ural 1251. Cemetery Manager

  1 /**
  2 Create By yzx - stupidboy
  3 */
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <deque>
  9 #include <vector>
 10 #include <queue>
 11 #include <iostream>
 12 #include <algorithm>
 13 #include <map>
 14 #include <set>
 15 #include <ctime>
 16 #include <iomanip>
 17 using namespace std;
 18 typedef long long LL;
 19 typedef double DB;
 20 #define MIT (2147483647)
 21 #define INF (1000000001)
 22 #define MLL (1000000000000000001LL)
 23 #define sz(x) ((int) (x).size())
 24 #define clr(x, y) memset(x, y, sizeof(x))
 25 #define puf push_front
 26 #define pub push_back
 27 #define pof pop_front
 28 #define pob pop_back
 29 #define mk make_pair
 30 
 31 inline int Getint()
 32 {
 33     int Ret = 0;
 34     char Ch = ‘ ‘;
 35     bool Flag = 0;
 36     while(!(Ch >= ‘0‘ && Ch <= ‘9‘))
 37     {
 38         if(Ch == ‘-‘) Flag ^= 1;
 39         Ch = getchar();
 40     }
 41     while(Ch >= ‘0‘ && Ch <= ‘9‘)
 42     {
 43         Ret = Ret * 10 + Ch - ‘0‘;
 44         Ch = getchar();
 45     }
 46     return Flag ? -Ret : Ret;
 47 }
 48 
 49 const int N = 110, MAXINDEX = 15010, LEN = 1000, ILEN = 100;
 50 class Node
 51 {
 52 private :
 53     int x, y;
 54     
 55 public :
 56     Node() {}
 57     Node(int tx, int ty)
 58     {
 59         x = tx, y = ty;
 60     }
 61     
 62     inline bool operator <(const Node &t) const
 63     {
 64         if(x != t.x) return x > t.x;
 65         return y > t.y;
 66     }
 67     
 68     inline int GetRow()
 69     {
 70         return x;
 71     }
 72     
 73     inline int GetCol()
 74     {
 75         return y;
 76     }
 77     
 78     inline int GetTime()
 79     {
 80         return x;
 81     }
 82     
 83     inline int GetIndex()
 84     {
 85         return y;
 86     }
 87 } ;
 88 class Heap
 89 {
 90 private :
 91     priority_queue<Node> Store;
 92     
 93 public :
 94     inline void Push(int x, int y)
 95     {
 96         Store.push(Node(x, y));
 97     }
 98     
 99     inline void Push(const Node &x)
100     {
101         Store.push(x);
102     }
103     
104     inline void Pop()
105     {
106         Store.pop();
107     }
108     
109     inline Node GetTop()
110     {
111         return Store.top();
112     }
113     
114     inline bool Empty()
115     {
116         return Store.empty();
117     }
118 } deadtime, emptylist;
119 int n, m, cnttombs;
120 int endtime[MAXINDEX], graph[N][N];
121 Node where[MAXINDEX];
122 bool have[MAXINDEX];
123 int ans;
124 
125 inline void Input()
126 {
127     scanf("%d%d", &n, &m);
128 }
129 
130 inline void Dug(int now)
131 {
132     while(!deadtime.Empty())
133     {
134         Node t = deadtime.GetTop();
135         int idx = t.GetIndex(), deadline = t.GetTime();
136         if(!have[idx] || endtime[idx] != deadline)
137             deadtime.Pop();
138         else if(deadline >= now) break;
139         else
140         {
141             emptylist.Push(where[idx]);
142             graph[where[idx].GetRow()][where[idx].GetCol()] = -1;
143             where[idx] = Node(-1, -1);
144             endtime[idx] = -1, have[idx] = 0;
145             deadtime.Pop();
146         }
147     }
148 }
149 
150 inline bool AddTomb(int now)
151 {
152     bool ret = 0;
153     cnttombs++;
154     while(!ret && !emptylist.Empty())
155     {
156         Node t = emptylist.GetTop();
157         int x = t.GetRow(), y = t.GetCol();
158         graph[x][y] = cnttombs, where[cnttombs] = t;
159         have[cnttombs] = 1, endtime[cnttombs] = now + LEN;
160         deadtime.Push(endtime[cnttombs], cnttombs);
161         emptylist.Pop();
162         ret = 1;
163     }
164     return ret;
165 }
166 
167 inline bool Check(int x, int y)
168 {
169     if(x < 0 || x >= n || y < 0 || y >= m) return 0;
170     if(!graph[x][y] || !have[graph[x][y]]) return 0;
171     return 1;
172 }
173 
174 inline void Visit(int now, int idx)
175 {
176     const int     DX[] = {-1, 0, 1, 0, -1, -1, 1, 1}, 
177                 DY[] = {0, -1, 0, 1, -1, 1, -1, 1};
178     if(!have[idx]) return;
179     int x = where[idx].GetRow(), y = where[idx].GetCol();
180     endtime[idx] = max(endtime[idx], now + LEN);
181     deadtime.Push(endtime[idx], idx);
182     for(int t = 0; t < 8; ++ t)
183     {
184         int dx = x + DX[t], dy = y + DY[t];
185         if(!Check(dx, dy)) continue;
186         endtime[graph[dx][dy]] = max(endtime[graph[dx][dy]], now + ILEN);
187         deadtime.Push(endtime[graph[dx][dy]], graph[dx][dy]);
188     }
189 }
190 
191 inline void Solve()
192 {
193     for(int i = 0; i < n; i++)
194         for(int j = 0; j < m; j++)
195             emptylist.Push(i, j);
196     
197     char type;
198     int t, idx;
199     while(scanf("%d", &t) == 1)
200     {
201         for(type = ‘ ‘; type != ‘v‘ && type != ‘d‘; type = getchar());
202         Dug(t);
203         if(type == ‘d‘)
204         {
205             bool ret = AddTomb(t);
206             ans += !ret;
207         }
208         else
209         {
210             scanf("%d", &idx);
211             Visit(t, idx);
212         }
213     }
214     
215     printf("%d\n", ans);
216 }
217 
218 int main()
219 {
220     freopen("a.in", "r", stdin);
221     Input();
222     Solve();
223     return 0;
224 }