Submission #291458

#	Time	Username	Problem	Language	Result	Execution time	Memory
291458		TadijaSebez	Dragon 2 (JOI17_dragon2)	C++11	100 / 100	761 ms	15992 KiB

dragon2

#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);
	}
	BT1.init();BT2.init();
	for(int i=1;i<=n;i++)BT1.Add(idx[i],1);
	for(int j=1;j<=n;j++){
		int i=srt[j].second;
		for(pii qu:R[c[i]]){
			int o=Find({qu.first,dir[i]});
			if(side[i])ans[qu.second]+=BT1.Get(fir[qu.first],o-1);
			else ans[qu.second]+=BT2.Get(o,las[qu.first]);
		}
		BT1.Add(idx[i],-1);
		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);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40