[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
题意:给一个方格的1E9*1E9的地图,以及若干炸弹,每个炸弹的功能是将某行/某列的所有东西消灭,求若干炸弹依次下去,每次消灭了多少东西……
STL硬搞即可……
 1 #include <cstdio>
 2 #include <set>
 3 #include <map>
 4 
 5 using namespace std;
 6 typedef multiset<int> sint;
 7 typedef map<int, multiset<int> > line;
 8 
 9 line x;
10 line y;
11 
12 int bomb(line &x, line &y, int pos) {
13     int ret = x[pos].size();
14     for (sint::iterator ii = x[pos].begin();
15             ii != x[pos].end();
16             ii++) {
17         y[*ii].erase(pos);
18     }
19     x[pos].clear();
20     return ret;
21 }
22 
23 int main() {
24     for (;;) {
25         int n,m;
26         scanf("%d%d",&n,&m);
27         if (n + m == 0break;
28         x.clear();
29         y.clear();
30         while (n--) {
31             int tx,ty;
32             scanf("%d%d",&tx,&ty);
33             x[tx].insert(ty);
34             y[ty].insert(tx);
35         }
36         while (m--) {
37             int ctrl,pos;
38             scanf("%d%d",&ctrl,&pos);
39             printf("%d\n",ctrl == 0 ? bomb(x,y,pos) : bomb(y,x,pos));
40         }
41         printf("\n");
42     }
43     return 0;
44 }
posted on 2011-09-10 17:46 sweetsc 阅读(948) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: