This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
struct pt{ll x,y;pt(ll a=0,ll b=0):x(a),y(b){}};
ll cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
bool operator < (pt a,pt b){return cross(a,b)<0;}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
const int N=30050;
pt pts[N],X,Y,dir[N];
pair<int,pt> ord[N];
pair<pt,int> srt[N];
int fir[N],las[N],sz[N],c[N],side[N],idx[N],n,m,q;
int Find(pair<int,pt> p){return lower_bound(ord+1,ord+1+n,p)-ord;}
vector<pii> E[N],R[N];
struct BIT{
int sum[N];
void init(){for(int i=0;i<N;i++)sum[i]=0;}
BIT(){init();}
void Add(int i,int f){for(;i<N;i+=i&-i)sum[i]+=f;}
int Get(int i){int ans=0;for(;i;i-=i&-i)ans+=sum[i];return ans;}
int Get(int l,int r){return Get(r)-Get(l-1);}
}BT1,BT2;
const int M=100050;
ll ans[M];
int skip[M];
int main(){
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld %lld %i",&pts[i].x,&pts[i].y,&c[i]);
scanf("%lld %lld",&X.x,&X.y);
scanf("%lld %lld",&Y.x,&Y.y);
for(int i=1;i<=n;i++){
side[i]=(Y-X)<(pts[i]-X);
dir[i]=side[i]?pts[i]-Y:Y-pts[i];
ord[i]={c[i],dir[i]};
}
sort(ord+1,ord+1+n);
for(int i=1;i<=n;i++)idx[i]=Find({c[i],dir[i]});
for(int i=1;i<=m;i++)fir[i]=Find({i,Y-X});fir[m+1]=n+1;
for(int i=1;i<=m;i++)sz[i]=fir[i+1]-fir[i],las[i]=fir[i+1]-1;
for(int i=1;i<=n;i++)srt[i]={side[i]?pts[i]-X:X-pts[i],i};
sort(srt+1,srt+1+n);
scanf("%i",&q);
map<pii,int> was;
for(int i=1,a,b;i<=q;i++){
scanf("%i %i",&a,&b);
if(was[{a,b}]){
skip[i]=was[{a,b}];
continue;
}
was[{a,b}]=i;
//if(sz[a]<sz[b])
E[a].pb({b,i});
//else R[b].pb({a,i});
}
BT1.init();BT2.init();
for(int i=1;i<=n;i++)if(!side[i])BT2.Add(idx[i],1);
for(int j=1;j<=n;j++){
int i=srt[j].second;
for(pii qu:E[c[i]]){
int o=Find({qu.first,dir[i]});
ans[qu.second]+=BT1.Get(o,las[qu.first])+BT2.Get(fir[qu.first],o-1);
}
if(side[i])BT1.Add(idx[i],1);
else BT2.Add(idx[i],-1);
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[skip[i]?skip[i]:i]);
return 0;
}
Compilation message (stderr)
dragon2.cpp: In function 'int main()':
dragon2.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
40 | for(int i=1;i<=m;i++)fir[i]=Find({i,Y-X});fir[m+1]=n+1;
| ^~~
dragon2.cpp:40:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
40 | for(int i=1;i<=m;i++)fir[i]=Find({i,Y-X});fir[m+1]=n+1;
| ^~~
dragon2.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
29 | scanf("%i %i",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
dragon2.cpp:30:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
30 | for(int i=1;i<=n;i++)scanf("%lld %lld %i",&pts[i].x,&pts[i].y,&c[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
31 | scanf("%lld %lld",&X.x,&X.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
32 | scanf("%lld %lld",&Y.x,&Y.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%i",&q);
| ~~~~~^~~~~~~~~
dragon2.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%i %i",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |