[破碎的状态] cf 101630A
题意:
给你n个操作
1,放个靶子上去,保证靶子不重叠
2,丢个飞镖,如果扎中靶子,输出什么时候放的这个靶子;然后移除这个靶子
算法:
离散化
然后直接线段树维护vector(或者set)就过了...........
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<math.h> #include<time.h> #include<vector> #include<bitset> #include<memory> #include<utility> #include<fstream> #include<stdio.h> #include<sstream> #include<iostream> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; int oper[200005],x[200005],y[200005]; int z[400005]; vector<int> v[1<<21]; void change(int num,int l,int r,int l0,int r0,int val,int k) { if ((l0<=l)&&(r<=r0)) { if (k==1) { v[num].push_back(val); } else { int i; for (i=0;i<v[num].size()-1;i++) { if (v[num][i]==val) { swap(v[num][i],v[num][i+1]); } } v[num].pop_back(); } return; } int mid=(l+r)/2; if (l0<mid) change(num*2+1,l,mid,l0,r0,val,k); if (mid<r0) change(num*2+2,mid,r,l0,r0,val,k); } inline bool in_circle(int a,int b) { long long t=(long long)(x[a]-x[b])*(x[a]-x[b])+(long long)(y[a]-y[b])*(y[a]-y[b]); long long t2=(long long)y[a]*y[a]; return t<t2; } int query(int num,int l,int r,int k,int id) { int i; for (i=0;i<v[num].size();i++) { if (in_circle(v[num][i],id)) return v[num][i]; } if (l==r-1) { return -1; } int mid=(l+r)/2; if (k<mid) { return query(num*2+1,l,mid,k,id); } else { return query(num*2+2,mid,r,k,id); } } int main() { #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; scanf("%d",&n); int i; int cnt=0; for (i=0;i<n;i++) { scanf("%d%d%d",&oper[i],&x[i],&y[i]); if (oper[i]==1) { z[cnt++]=x[i]-y[i]+1; z[cnt++]=x[i]+y[i]-1; } else { z[cnt++]=x[i]; } } sort(z,z+cnt); cnt=unique(z,z+cnt)-z; for (i=0;i<n;i++) { if (oper[i]==1) { change(0,0,cnt,lower_bound(z,z+cnt,x[i]-y[i]+1)-z,lower_bound(z,z+cnt,x[i]+y[i]-1)-z+1,i,1); } else { int ans=query(0,0,cnt,lower_bound(z,z+cnt,x[i])-z,i); if (ans!=-1) { change(0,0,cnt,lower_bound(z,z+cnt,x[ans]-y[ans]+1)-z,lower_bound(z,z+cnt,x[ans]+y[ans]-1)-z+1,ans,-1); } if (ans>=0) ans++; printf("%d\n",ans); } } return 0; }
Aug 20, 2022 02:05:11 AM
The NJMCDirect online portal has eventually replaced the old queuing system. Whenever once violates the traffic or parking rules. The traffic officers provide a traffic ticket stating your offenses and fine to pay. These compel you to pay the fines within the stated time frame. Violators need to visit the court and queue for long hours. njmcdirect However, the New Jersey Meadowlands Commission (N.J.M.C.) has digitalized their traffic ticket system. They have implemented a new online portal, NJMCDirect. Here traffic law offenders can pay their fines online using their devices such as mobile phones, laptops, etc.