Submission #1240297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240297		PenguinsAreCute	Dragon 2 (JOI17_dragon2)	C++17	0 / 100	364 ms	9156 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using cp = complex<long double>;
ld PI = acos(-1);
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;
	}
};
/*
Seriously?
O(cbrt(N^4 * Q * log^2 N))???
*/
const int K = 400;
int main() {
	int n, m;
	cin >> n >> m;
	vector<cp> dragon[m];
	for(int i=0;i<n;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		dragon[c-1].push_back({a,b});
	}
	if(1) {
		cp st, nd;
		int d1, e1, d2, e2;
		cin >> d1 >> e1 >> d2 >> e2;
		st = cp(d1,e1);
		nd = cp(d2,e2);
		for(int i=0;i<m;i++)
			for(auto &j: dragon[i])
				j = (j - st) / (nd - st);
	}
	int q;
	cin >> q;
	for(int f,g;q--;) {
		cin >> f >> g;
		f--; g--;
		vector<tuple<ld,ld,int>> help;
		vector<ld> disc;
		for(auto c: dragon[g]) {
			help.push_back({arg(c), arg(cp(1) - c), 0});
			disc.push_back(arg(cp(1) - c));
		}
		for(auto c: dragon[f]) {
			long double fi = min(arg(c), arg(-c));
			long double se = min(arg(c-cp(1)), arg(cp(1)-c));
			help.push_back({fi, se, 1});
			help.push_back({fi, se + PI, -1});
			help.push_back({fi + PI, se, -1});
			help.push_back({fi + PI, se + PI, 1});
			disc.push_back(se);
			disc.push_back(se+PI);
		}
		fenwick fw(disc.size());
		sort(disc.begin(),disc.end());
		sort(help.begin(),help.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";
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:33:40: warning: narrowing conversion of 'a' from 'int' to 'long double' [-Wnarrowing]
   33 |                 dragon[c-1].push_back({a,b});
      |                                        ^
dragon2.cpp:33:42: warning: narrowing conversion of 'b' from 'int' to 'long double' [-Wnarrowing]
   33 |                 dragon[c-1].push_back({a,b});
      |                                          ^

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