Documentation/docs-sonyckson/1037.cpp

   1 #include <algorithm>
   2 #include <vector>
   3 #include <set>
   4 #include <string>
   5 #include <fstream>
   6 #include <iostream>
   7 #include <iomanip>
   8 #include <map>
   9 #include <stack>
  10 #include <sstream>
  11 #include <queue>
  12
  13 #include <cmath>
  14 #include <cstdio>
  15 #include <cctype>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <cassert>
  19 #define REP(i, n) for(int i=0;i<int(n);i++)
  20 #define foreach(it, c)  for(typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  21 #define ALL(x)   (x).begin(),(x).end()
  22 #define SORT(x) sort(ALL(x))
  23 using namespace std;
  24 #define VI vector<int>
  25 #define VS vector<string>
  26 #define PB push_back
  27 #define ll long long
  28 #define VP vector<pair<int,int> >
  29 template <typename T> void enqueue(vector< T > &H, T par){
  30         H.PB(par);
  31         int e = H.size() -1 ;
  32         while(e != 1  && par < H[e/2] ){
  33                 swap(H[e], H[e/2]);
  34                 e /= 2;
  35         }
  36 }
  37 template <typename T> void dequeue(vector< T > &H){
  38         if( H.size() == 1 ) return;
  39         int f = 1;
  40         int e = H.size() -1 ;
  41         swap(H[f], H[e]);
  42         H.pop_back();
  43         e --;
  44         while(1){
  45                 int d = f*2;
  46                 if( d > e ) break;
  47                 if( d+1 <= e && H[d] > H[d+1] ) d++;
  48                 if( H[d] > H[f] ) break;
  49                 swap(H[f], H[d]);
  50                 f = d;
  51         }
  52 }
  53
  54
  55 int main(){
  56         int i,j ,k;
  57
  58         int aux;string s;
  59         vector<int> H1;
  60         vector<pair<int,int > > H2;
  61         H1.PB(10000000); // DUMMY
  62         for(i=1;i<30001;i++)enqueue(H1,i);
  63         H2.PB(make_pair(1000000, 1234114));
  64         int ultima[30010];
  65         REP(i, 30010) ultima[i] = -1000;
  66         while(cin >> aux){
  67                 cin >> s;
  68                 if( s == "." ){
  69                         int c ; cin >> c;
  70                         if( aux - 600 < ultima[c] ){
  71                                 printf("+\n");
  72                                 ultima[c] = aux;
  73                         }else{
  74                                 printf("-\n");
  75                         }
  76                 }else{
  77                         while(H2.size() > 1){
  78                                 int t = H2[1].first;
  79                                 int c = H2[1].second;
  80                                 if( t < ultima[c] ){
  81                                         dequeue(H2);
  82                                         enqueue(H2, make_pair(ultima[c], c));
  83                                 }else{
  84                                         if( aux - 600 >= ultima[c] ){
  85                                                 dequeue(H2);
  86                                                 enqueue(H1, c);
  87                                         }else break;
  88                                 }
  89                         }
  90                         int r = H1[1];
  91                         printf("%i\n", r);
  92                         dequeue(H1);
  93                         enqueue(H2, make_pair(aux, r));
  94                         ultima[r] = aux;
  95
  96                 }
  97         }return 0;
  98 }