Submission #10754117


Source Code Expand

Copy
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using D=long double;
using C=complex<D>;
const D eps=1e-40;
inline D cross(C a,C b){
	return a.real()*b.imag()-a.imag()*b.real();
}
inline int ccw(C a,C b,C c){
	b-=a;c-=a;
	if(cross(b,c)>eps)return 1;
	if(cross(b,c)<-eps)return -1;
	return 0;
}
struct BIT{
	vector<int> bit;
	BIT(int n){
		bit.resize(++n);
	}
	void add(int k,int x){
		for(++k;k<bit.size();k+=k&-k){
			bit[k]+=x;
		}
	}
	int sum(int k){
		int res=0;
		for(++k;k>0;k-=k&-k){
			res+=bit[k];
		}
		return res;
	}
};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<D> a(n),b(n);
	vector<int> c(n),sz(m);
	vector<C> p(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];--c[i];
		p[i]=C(a[i],b[i]);
		sz[c[i]]++;
	}
	D d1,e1,d2,e2;cin>>d1>>e1>>d2>>e2;
	C p1=C(d1,e1),p2=C(d2,e2);
	vector<vector<pair<D,D>>> vaa(m),vba(m);
	vector<vector<D>> vab(m),vbb(m);
	vector<D> bs;
	for(int i=0;i<n;i++){
		if(ccw(p1,p[i],p2)>0){
			D s=arg((p1-p[i])/(p2-p1)),t=arg((p2-p[i])/(p2-p1));
			vaa[c[i]].eb(s,t);
			vab[c[i]].eb(t);
			bs.eb(t);
		}else{
			D s=arg((p[i]-p1)/(p2-p1)),t=arg((p[i]-p2)/(p2-p1));
			vba[c[i]].eb(s,t);
			vbb[c[i]].eb(t);
			bs.eb(t);
		}
	}
	sort(all(bs));
	bs.erase(unique(all(bs)),bs.end());
	BIT bit(bs.size()+10);
	for(int i=0;i<m;i++){
		sort(all(vaa[i]));
		sort(all(vab[i]));
		sort(all(vba[i]));
		sort(all(vbb[i]));
	}
	int q;cin>>q;
	vector<int> f(q),g(q);
	vector<vector<pair<pair<D,D>,int>>> qa1(m),qa2(m),qb1(m),qb2(m);
	vector<ll> res(q);
	for(int j=0;j<q;j++){
		cin>>f[j]>>g[j];--f[j];--g[j];
		res[j]=(ll)vaa[f[j]].size()*vba[g[j]].size()+(ll)vba[f[j]].size()*vaa[g[j]].size();
		if(sz[f[j]]<=sz[g[j]]){
			for(auto &e:vaa[f[j]]){
				res[j]-=vba[g[j]].end()-lower_bound(all(vba[g[j]]),e);
				res[j]-=lower_bound(all(vbb[g[j]]),e.second)-vbb[g[j]].begin();
				qa1[g[j]].eb(e,j);
			}
			for(auto &e:vba[f[j]]){
				res[j]-=lower_bound(all(vaa[g[j]]),e)-vaa[g[j]].begin();
				res[j]-=vab[g[j]].end()-lower_bound(all(vab[g[j]]),e.second);
				qb1[g[j]].eb(e,j);
			}
		}else{
			for(auto &e:vaa[g[j]]){
				res[j]-=vba[f[j]].end()-lower_bound(all(vba[f[j]]),e);
				res[j]-=lower_bound(all(vbb[f[j]]),e.second)-vbb[f[j]].begin();
				qa2[f[j]].eb(e,j);
			}
			for(auto &e:vba[g[j]]){
				res[j]-=lower_bound(all(vaa[f[j]]),e)-vaa[f[j]].begin();
				res[j]-=vab[f[j]].end()-lower_bound(all(vab[f[j]]),e.second);
				qb2[f[j]].eb(e,j);
			}
		}
	}
	auto getidx=[&](D x){int r=lower_bound(all(bs),x-eps)-bs.begin();return r;};
	for(int i=0;i<m;i++){
		sort(all(qa1[i]));
		sort(all(qb1[i]));
		sort(all(qa2[i]));
		sort(all(qb2[i]));
		reverse(all(qa1[i]));
		reverse(all(qb2[i]));
		auto calca=[&](vector<vector<pair<pair<D,D>,int>>>& qa,vector<vector<pair<D,D>>>& vv){
			int id=0;
			for(auto &e:qa[i]){
				while(id<vv[i].size()&&vv[i][id].first>e.first.first){
					bit.add(getidx(vv[i][id].second),1);
					id++;
				}
				res[e.second]+=bit.sum(getidx(e.first.second));
			}
			for(int j=0;j<id;j++){
				bit.add(getidx(vv[i][j].second),-1);
			}
		};
		auto calcb=[&](vector<vector<pair<pair<D,D>,int>>>& qb,vector<vector<pair<D,D>>>& vv){
			int id=0;
			for(auto &e:qb[i]){
				while(id<vv[i].size()&&vv[i][id].first<e.first.first){
					bit.add(getidx(vv[i][id].second),1);
					id++;
				}
				res[e.second]+=bit.sum(bs.size())-bit.sum(getidx(e.first.second));
			}
			for(int j=0;j<id;j++){
				bit.add(getidx(vv[i][j].second),-1);
			}
		};
		calcb(qb1,vba);
		calcb(qa2,vaa);
		reverse(all(vaa[i]));
		reverse(all(vba[i]));
		calca(qa1,vaa);
		calca(qb2,vba);
	}
	for(int i=0;i<q;i++){
		cout<<res[i]<<'\n';
	}
}

Submission Info

Submission Time
Task L - ドラゴン 2 (Dragon 2)
User TAISA_
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3828 Byte
Status
Exec Time 984 ms
Memory 170872 KB

Judge Result

Set Name Score / Max Score Test Cases
Subtask01 15 / 15 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
Subtask02 45 / 45 sample-01.txt, sample-02.txt, sample-03.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt
Subtask03 40 / 40 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, 03-26.txt, 03-27.txt, 03-28.txt, 03-29.txt
Case Name Status Exec Time Memory
01-01.txt 7 ms 896 KB
01-02.txt 10 ms 1536 KB
01-03.txt 42 ms 9472 KB
01-04.txt 85 ms 17024 KB
01-05.txt 44 ms 6400 KB
01-06.txt 6 ms 1408 KB
01-07.txt 6 ms 1408 KB
01-08.txt 5 ms 896 KB
01-09.txt 4 ms 768 KB
01-10.txt 4 ms 896 KB
02-01.txt 47 ms 5736 KB
02-02.txt 102 ms 13800 KB
02-03.txt 52 ms 6520 KB
02-04.txt 38 ms 5368 KB
02-05.txt 42 ms 10744 KB
02-06.txt 42 ms 5484 KB
02-07.txt 42 ms 5484 KB
02-08.txt 41 ms 5484 KB
02-09.txt 34 ms 5372 KB
02-10.txt 32 ms 5492 KB
03-01.txt 47 ms 5736 KB
03-02.txt 102 ms 13424 KB
03-03.txt 578 ms 89488 KB
03-04.txt 984 ms 170872 KB
03-05.txt 154 ms 22520 KB
03-06.txt 93 ms 15480 KB
03-07.txt 50 ms 12152 KB
03-08.txt 47 ms 12152 KB
03-09.txt 92 ms 14064 KB
03-10.txt 81 ms 13296 KB
03-11.txt 76 ms 13172 KB
03-12.txt 95 ms 15540 KB
03-13.txt 539 ms 103160 KB
03-14.txt 78 ms 13432 KB
03-15.txt 81 ms 13944 KB
03-16.txt 90 ms 15608 KB
03-17.txt 96 ms 15480 KB
03-18.txt 527 ms 88596 KB
03-19.txt 604 ms 112760 KB
03-20.txt 563 ms 103032 KB
03-21.txt 99 ms 15216 KB
03-22.txt 122 ms 17644 KB
03-23.txt 140 ms 21728 KB
03-24.txt 55 ms 8948 KB
03-25.txt 54 ms 8952 KB
03-26.txt 54 ms 9208 KB
03-27.txt 54 ms 8944 KB
03-28.txt 55 ms 9464 KB
03-29.txt 54 ms 8952 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB
sample-03.txt 1 ms 256 KB