Submission #1240394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240394		PenguinsAreCute	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	2274 ms	16992 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;
const int K = 149;
struct slope {
	int x, y;
	slope(int _x, int _y): x(_x), y(_y) {}
	slope operator - () {return slope(-x,-y);}
};
struct fenwick {
	int n;
	vector<int> fw;
	fenwick(int _n): n(_n+1), fw(_n+1,0) {}
	void up(int x, int u) {
		for(x++;x<n;x+=(x&(-x)))
			fw[x] += u;
	}
	int qry(int x) {
		int ans = 0;
		for(x++;x;x-=(x&(-x)))
			ans += fw[x];
		return ans;
	}
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int,int,int,int>> dragon[m];
	if(1) {
		int a[n], b[n], c[n];
		for(int i=0;i<n;i++) {
			cin >> a[i] >> b[i] >> c[i];
			c[i]--;
		}
		int d1, e1, d2, e2;
		cin >> d1 >> e1 >> d2 >> e2;
		auto cmp0 = [](slope a, slope b) {
			return (1LL * a.y * b.x < 1LL * a.x * b.y);
		};
		auto cmp1 = [&cmp0,d1,e1,d2,e2](slope x, slope y) {
			slope z(d2 - d1, e2 - e1);
			if(cmp0(x,z) == cmp0(y,z))
				return cmp0(x,y);
			return cmp0(x,z);
		};
		auto cmp2 = [&cmp0,d1,e1,d2,e2](slope x, slope y) {
			slope z(d1 - d2, e1 - e2);
			if(cmp0(x,z) == cmp0(y,z))
				return cmp0(x,y);
			return cmp0(x,z);
		};
		vector<slope> disc1, disc2;
		for(int i=0;i<n;i++) {
			disc1.push_back(slope(a[i]-d1,b[i]-e1));
			disc1.push_back(-slope(a[i]-d1,b[i]-e1));
			disc2.push_back(slope(a[i]-d2,b[i]-e2));
			disc2.push_back(-slope(a[i]-d2,b[i]-e2));
		}
		sort(disc1.begin(),disc1.end(),cmp1);
		sort(disc2.begin(),disc2.end(),cmp2);
		for(int i=0;i<n;i++) {
			int p1 = lower_bound(disc1.begin(),disc1.end(),slope(a[i]-d1,b[i]-e1),cmp1)-disc1.begin();
			int n1 = lower_bound(disc1.begin(),disc1.end(),-slope(a[i]-d1,b[i]-e1),cmp1)-disc1.begin();
			int p2 = lower_bound(disc2.begin(),disc2.end(),slope(a[i]-d2,b[i]-e2),cmp2)-disc2.begin();
			int n2 = lower_bound(disc2.begin(),disc2.end(),-slope(a[i]-d2,b[i]-e2),cmp2)-disc2.begin();
			dragon[c[i]].push_back({p1,n1,p2,n2});
		}
	}

	vector<int> spec;
	for(int i=0;i<m;i++)
		if(dragon[i].size() > K)
			spec.push_back(i);
	int s = spec.size();
	int ans1[s][m], ans2[m][s];
	memset(ans1,0,sizeof(ans1));
	memset(ans2,0,sizeof(ans2));
	for(int i=0;i<s;i++) {
		vector<tuple<int,int,int>> help;
		int g = spec[i];
		for(auto [p1, n1, p2, n2]: dragon[g])
			help.push_back({p1, p2, 0});
		for(int f=0;f<m;f++)
			if(f != g && dragon[f].size() <= K)
				for(auto [p1, n1, p2, n2]: dragon[f]) {
					int fi = min(p1, n1);
					int se = min(p2, n2);
					help.push_back({fi, se, f+1});
					help.push_back({fi, p2^n2^se, -f-1});
					help.push_back({p1^n1^fi, se, -f-1});
					help.push_back({p1^n1^fi, p2^n2^se, f+1});
				}
		fenwick fw(2*n);
		sort(help.begin(),help.end());
		int ans = 0;
		for(auto [fi, se, tp]: help) {
			if(tp == 0)
				fw.up(se, 1);
			else
				ans2[abs(tp)-1][i] += (tp>0?1:-1) * fw.qry(se);
		}
	}
	for(int i=0;i<s;i++) {
		vector<tuple<int,int,int>> help;
		int f = spec[i];
		for(auto [p1, n1, p2, n2]: dragon[f]) {
			int fi = min(p1, n1);
			int se = min(p2, n2);
			help.push_back({fi, se, 0});
		}
		for(int g=0;g<m;g++)
			if(g != f)
				for(auto [p1, n1, p2, n2]: dragon[g]) {
					help.push_back({p1,p2,g+1});
					if(n1 < p1)
						help.push_back({n1,p2,-(g+1)});
					if(n2 < p2)
						help.push_back({p1,n2,-(g+1)});
					if(n1 < p1 && n2 < p2)
						help.push_back({n1,n2,g+1});
				}
		fenwick fw(2 * n);
		sort(help.begin(),help.end());
		int ans = 0;
		for(auto [fi, se, tp]: help) {
			if(tp == 0)
				fw.up(se, 1);
			else
				ans1[i][abs(tp)-1] += (tp>0?1:-1) * fw.qry(se);
		}
	}

	int q;
	cin >> q;
	for(int f,g;q--;) {
		cin >> f >> g;
		f--; g--;
		if(dragon[f].size() <= K && dragon[g].size() <= K) {
			vector<tuple<int,int,int>> help;
			vector<int> disc;
			for(auto [p1, n1, p2, n2]: dragon[g]) {
				help.push_back({p1, p2, 0});
				disc.push_back(p2);
			}
			for(auto [p1, n1, p2, n2]: dragon[f]) {
				int fi = min(p1, n1);
				int se = min(p2, n2);
				help.push_back({fi, se, 1});
				help.push_back({fi, p2^n2^se, -1});
				help.push_back({p1^n1^fi, se, -1});
				help.push_back({p1^n1^fi, p2^n2^se, 1});
				disc.push_back(se);
				disc.push_back(p2^n2^se);
			}
			fenwick fw(disc.size());
			sort(help.begin(),help.end());
			sort(disc.begin(),disc.end());
			int ans = 0;
			for(auto [fi, se, tp]: help) {
				int seNw = lower_bound(disc.begin(),disc.end(),se) - disc.begin();
				if(tp == 0)
					fw.up(seNw, 1);
				else
					ans += tp * fw.qry(seNw);
			}
			cout << ans << "\n";
		} else if(dragon[f].size() > K)
			cout << ans1[lower_bound(spec.begin(),spec.end(),f)-spec.begin()][g] << "\n";
		else
			cout << ans2[f][lower_bound(spec.begin(),spec.end(),g)-spec.begin()] << "\n";
	}
}

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