hdu 4022 Bombing (离散化)
wa了两次,原因是在同一个点可能有多个基地。。。
所以用set 是错误的,应该用multiset
然后因为这道题看到了map+set实现离散化的另外一种写法
我的代码:
/*************************************************************************
> File Name: code/hdoj/4022.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月01日 星期六 04时37分20秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int N=2E5+7;
24const int inf = 0x7fffffff;
1map<int,int>xmap,ymap;
2multiset<int>x[N];
3multiset<int>y[N];
4int main()
5{
6 int n,m;
7 while (scanf("%d %d",&n,&m)!=EOF)
8 {
9 if (n==0&&m==0) break;
10 for ( int i = 1 ; i <= n ; i++)
11 {
12 x[i].clear();
13 y[i].clear();
14 }
15 xmap.clear();
16 ymap.clear();
17 int tx,ty;
18 int cntx=0,cnty=0;
19 for ( int i = 1 ; i <= n ; i++ )
20 {
21 scanf("%d %d",&tx,&ty);
22 if (!xmap[tx]) xmap[tx]=++cntx;
23 if (!ymap[ty]) ymap[ty]=++cnty;
24 x[xmap[tx]].insert(ymap[ty]);
25 y[ymap[ty]].insert(xmap[tx]);
26 }
27 int c,d;
28 set<int>::iterator it;
29 for ( int i = 1; i <= m ; i++ )
30 {
31 scanf("%d %d",&c,&d);
32 if (c==0)
33 {
34 cout<<x[xmap[d]].size()<<endl;
35 for ( it = x[xmap[d]].begin();it!=x[xmap[d]].end();it++)
36 {
37 y[*it].erase(xmap[d]);
38 }
39 x[xmap[d]].clear();
40 }
41 else
42 {
43 cout<<y[ymap[d]].size()<<endl;
44 for ( it =y[ymap[d]].begin();it!=y[ymap[d]].end();it++)
45 {
46 x[*it].erase(ymap[d]);
1 }
2 y[ymap[d]].clear();
3 }
4 }
5 printf("\n");
6 }
return 0;
}