「vijos1066」弱弱的战壕
描述
永恒和mx正在玩一个即时战略游戏，名字嘛~~~~~~恕本人记性不好，忘了-_-b。
mx在他的基地附近建立了n个战壕，每个战壕都是一个独立的作战单位，射程可以达到无限（“mx不赢定了？！？”永恒ftING…@_@）。
但是，战壕有一个弱点，就是只能攻击它的左下方，说白了就是横纵坐标都不大于它的点（mx：“我的战壕为什么这么菜”ToT）。这样，永恒就可以从别的地方进攻摧毁战壕，从而消灭mx的部队。
战壕都有一个保护范围，同它的攻击范围一样，它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样，永恒就必须找到mx的战壕中保护对象最多的点，从而优先消灭它。
现在，由于永恒没有时间来计算，所以拜托你来完成这个任务：
给出这n个战壕的坐标xi、yi，要你求出保护对象个数为0，1，2……n-1的战壕的个数。
输入格式
第一行，一个正整数n（1<=n<=15000）
接下来n行，每行两个数xi,yi，代表第i个点的坐标
（1<=xi,yi<=32000）
注意：可能包含多重战壕的情况（即有数个点在同一坐标）
输出格式
输出n行，分别代表保护对象为0，1，2……n-1的战壕的个数。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int n,ans[15000]; struct node{int r,l,v;}tr[100001]; struct data{int x,y;}f[15000]; inline bool cmp(data a,data b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);} void buildtree(int size,int lf,int rt){ tr[size].v=0; tr[size].l=lf; tr[size].r=rt; if(lf==rt)return; int mid=(lf+rt)>>1; buildtree(size<<1,lf,mid); buildtree(size<<1|1,mid+1,rt); } void insert(int st,int ed,int size) { int mid=(tr[size].l+tr[size].r)>>1; if(tr[size].l==st&&tr[size].r==ed) { tr[size].v++; return; } else if(tr[size].r==tr[size].l)return; else if(ed<=mid)insert(st,ed,size<<1); else if(st>mid)insert(st,ed,size<<1|1); else { insert(st,mid,size<<1); insert(mid+1,ed,size<<1|1); } } int query(int x,int size){ if(tr[size].l==tr[size].r)return tr[size].v; int mid=(tr[size].l+tr[size].r)>>1; if(x<=mid)return tr[size].v+(query(x,size<<1)); else return tr[size].v+(query(x,size<<1|1)); } int main() { scanf("%d",&n); buildtree(1,0,32001); for(int i=0;i<n;i++) scanf("%d%d",&f[i].x,&f[i].y); sort(f,f+n,cmp); for(int i=0;i<n;i++) { ans[query(f[i].y,1)]++; insert(f[i].y,32001,1); } for(int i=0;i<n;i++) printf("%d\n",ans[i]); return 0; } |
本题暴力可过
Subscribe
计数器 9855276
OI 课件=>
OI 课件=>