Submission #413919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
413919	2021-05-29T17:18:47 Z	amoo_safar	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	871 ms	229372 KB

dragon2

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

pll operator-(pll A, pll B){ return pll(A.F - B.F, A.S - B.S); }
pll operator+(pll A, pll B){ return pll(A.F + B.F, A.S + B.S); }
ll Cross(pll A, pll B) { return A.F * B.S - A.S * B.F; }
bool CMP(pll A, pll B){
	return Cross(A, B) > 0;
}

int n, m;
// int att[N], def[N]
ll ans[N];
pll po[N];
int ty[N], cnt[N];
vector<int> V[N];

struct Fenwick {
	static const int DELTA = 2;

	vector<int> fen;
	int _N;
	Fenwick (){
	}
	void Set_Size(int _n){
		_N = _n + DELTA + 3;
		fen.resize(_N, 0);
	}
	void Add(int idx, int x){
		idx += DELTA;
		for(;idx < _N; idx += (idx & (-idx)))
			fen[idx] += x;
	}
	int Get(int idx){
		idx += DELTA;
		int res = 0;
		for(; idx; idx -= (idx & (-idx)))
			res += fen[idx];
		return res;
	}
};	
struct Half_Plane {
	pll O;
	vector<pll> vec;
	vector<int> ons;
	Fenwick fen;
	Half_Plane (){
		vec.clear();
		ons.clear();
	}
	void Set_Origin(pll X){ O = X; };
	void Add_Point(pll X){ vec.pb(X - O); };
	void Init(){
		sort(all(vec), CMP);
		fen.Set_Size(vec.size());
	}
	int Find(pll X){
		int pos = upper_bound(all(vec), X - O, CMP) - vec.begin();
		return pos - 1;
	}
	void On(pll X){
		int pos = Find(X);
		fen.Add(pos, +1); ons.pb(pos);
	}
	int Right(pll X){
		int pos = Find(X);
		return fen.Get(pos);
	}
	int Left(pll X){
		return ons.size() - Right(X);
	}
	void Reset(){
		for(auto pos : ons)
			fen.Add(pos, -1);
		ons.clear();
	}
};

struct CHF {
	Half_Plane H[N];
	CHF() {

	}
	void Set_Origin(pll X){	
		for(int i = 0; i < N; i++)
			H[i].Set_Origin(X);
	}
	void Add_Point(pll X, int col){ H[col].Add_Point(X); };
	void Init(){
		for(int i = 0; i < N; i++)
			H[i].Init();
	}
	void On(pll X, int col){
		H[col].On(X);
	}
	int Right(pll X, int col){
		return H[col].Right(X);
	}
	int Left(pll X, int col){
		return H[col].Left(X);
	}
	void Reset(){
		for(int i = 0; i < N; i++)
			H[i].Reset();
	}
};

int rem[N];
struct Solver {
	pll P[2];
	CHF D[2];
	CHF U[2];
	pll ln, P0, P1;
	struct Query {
		int oth, id;
		bool att;
	};
	vector<Query> Q[N];

	Solver (pll _P0, pll _P1){
		P[0] = _P0; P[1] = _P1;
		ln = P[1] - P[0]; // P0 -> P1

		D[0].Set_Origin(P[0]);
		D[1].Set_Origin(P[1]);
		U[0].Set_Origin(P[0]);
		U[1].Set_Origin(P[1]);
		for(int i = 1; i <= n; i++){
			if(Cross(ln, po[i] - P[0]) < 0){
				D[0].Add_Point(po[i], ty[i]);
				D[1].Add_Point(po[i], ty[i]);
			} else {
				U[0].Add_Point(po[i], ty[i]);
				U[1].Add_Point(po[i], ty[i]);
			}
		}
		D[0].Init(); D[1].Init();
		U[0].Init(); U[1].Init();
	}
	void Query_Att(int cf, int cb, int id){
		Q[cf].pb({cb, id, true});
	}
	void Query_Def(int cf, int cb, int id){
		Q[cb].pb({cf, id, false});
	}
	
	void Solve(){
		vector<int> I;
		for(int i = 1; i <= n; i++){
			if(Cross(ln, po[i] - P[0]) < 0){
				D[0].On(po[i], ty[i]);
				D[1].On(po[i], ty[i]);
			} else {
				I.pb(i);
			}
		}
		sort(all(I), [&](int i, int j){
			return Cross(ln, po[i] - P[0]) < Cross(ln, po[j] - P[0]);
		});
		// Getting D
		for(int i : I){
			for(auto [oth, id, att] : Q[ ty[i] ]){
				ans[id] += D[0].Right(P[0] + P[0] - po[i], oth);
				ans[id] += D[1].Left(P[1] + P[1] - po[i], oth);
			}
		}
		// Getting ATT
		for(int i : I) rem[ty[i]] ++;
		for(int i : I){
			for(auto [oth, id, att] : Q[ ty[i] ]){
				if(!att) continue;
				ans[id] += U[0].Left(po[i], oth);
				ans[id] += U[1].Right(po[i], oth);
				ans[id] += rem[oth];
			}
			U[0].On(po[i], ty[i]);
			U[1].On(po[i], ty[i]);
			rem[ty[i]] --;
		}
		U[0].Reset();
		U[1].Reset();
		// Getting DEF
		reverse(all(I));
		for(int i : I) rem[ty[i]] ++;
		for(int i : I){
			for(auto [oth, id, att] : Q[ ty[i] ]){
				if(att) continue;
				ans[id] += U[0].Right(po[i], oth);
				ans[id] += U[1].Left(po[i], oth);
				ans[id] += rem[oth];
			}
			U[0].On(po[i], ty[i]);
			U[1].On(po[i], ty[i]);
			rem[ty[i]] --;
		}
	}
};

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//
	// CHF HH;
	// HH.Set_Origin({3, 3});
	// HH.Add_Point({10, 10}, 1);
	// HH.Add_Point({10, 9}, 2);
	// HH.Add_Point({9, 10}, 3);
	// HH.Add_Point({3, 4}, 1);
	// HH.Init();
	// // for(auto [x, y] : HH.vec)
	// 	// cerr << "! " << x << ' ' << y << '\n';
	
	// HH.On({10, 9}, 2);
	// HH.On({10, 10}, 1);
	// debug( HH.Right({11, 10}, 1) );
	// debug( HH.Right({10, 11}, 2) );
	// exit(0);
	//

	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> po[i].F >> po[i].S >> ty[i];
		V[ty[i]].pb(i);
		cnt[ty[i]] ++;
	}
	pll C, D;
	cin >> C.F >> C.S >> D.F >> D.S;
	Solver A(C, D), B(D, C);
	int q, x, y;
	cin >> q;
	for(int i = 0; i < q; i++){
		cin >> x >> y;
		// if(i != 0) continue;
		if(cnt[x] <= cnt[y])
			A.Query_Att(x, y, i), B.Query_Att(x, y, i);
		else
			A.Query_Def(x, y, i), B.Query_Def(x, y, i);
		ans[i] -= 1ll * cnt[x] * cnt[y];
		// cout << (1ll * cnt[x] * cnt[y]) - A.Get(x, y) - B.Get(x, y) << '\n';
	}
	A.Solve();
	B.Solve();
	for(int i = 0; i < q; i++)
		cout << -ans[i] << '\n';
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	215280 KB	Output is correct
2	Correct	252 ms	215328 KB	Output is correct
3	Correct	287 ms	215588 KB	Output is correct
4	Correct	312 ms	220124 KB	Output is correct
5	Correct	282 ms	219776 KB	Output is correct
6	Correct	227 ms	215864 KB	Output is correct
7	Correct	236 ms	215908 KB	Output is correct
8	Correct	247 ms	215180 KB	Output is correct
9	Correct	252 ms	215236 KB	Output is correct
10	Correct	259 ms	215332 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	335 ms	219028 KB	Output is correct
2	Correct	371 ms	219388 KB	Output is correct
3	Correct	308 ms	219204 KB	Output is correct
4	Correct	297 ms	219788 KB	Output is correct
5	Correct	335 ms	223068 KB	Output is correct
6	Correct	313 ms	218560 KB	Output is correct
7	Correct	337 ms	218700 KB	Output is correct
8	Correct	314 ms	218440 KB	Output is correct
9	Correct	350 ms	218644 KB	Output is correct
10	Correct	307 ms	218596 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	215280 KB	Output is correct
2	Correct	252 ms	215328 KB	Output is correct
3	Correct	287 ms	215588 KB	Output is correct
4	Correct	312 ms	220124 KB	Output is correct
5	Correct	282 ms	219776 KB	Output is correct
6	Correct	227 ms	215864 KB	Output is correct
7	Correct	236 ms	215908 KB	Output is correct
8	Correct	247 ms	215180 KB	Output is correct
9	Correct	252 ms	215236 KB	Output is correct
10	Correct	259 ms	215332 KB	Output is correct
11	Correct	335 ms	219028 KB	Output is correct
12	Correct	371 ms	219388 KB	Output is correct
13	Correct	308 ms	219204 KB	Output is correct
14	Correct	297 ms	219788 KB	Output is correct
15	Correct	335 ms	223068 KB	Output is correct
16	Correct	313 ms	218560 KB	Output is correct
17	Correct	337 ms	218700 KB	Output is correct
18	Correct	314 ms	218440 KB	Output is correct
19	Correct	350 ms	218644 KB	Output is correct
20	Correct	307 ms	218596 KB	Output is correct
21	Correct	357 ms	219104 KB	Output is correct
22	Correct	349 ms	219408 KB	Output is correct
23	Correct	729 ms	219480 KB	Output is correct
24	Correct	871 ms	224440 KB	Output is correct
25	Correct	390 ms	225920 KB	Output is correct
26	Correct	411 ms	227752 KB	Output is correct
27	Correct	315 ms	225208 KB	Output is correct
28	Correct	333 ms	225172 KB	Output is correct
29	Correct	418 ms	225912 KB	Output is correct
30	Correct	389 ms	227520 KB	Output is correct
31	Correct	393 ms	227828 KB	Output is correct
32	Correct	382 ms	228008 KB	Output is correct
33	Correct	704 ms	228084 KB	Output is correct
34	Correct	386 ms	228004 KB	Output is correct
35	Correct	402 ms	228720 KB	Output is correct
36	Correct	415 ms	229116 KB	Output is correct
37	Correct	441 ms	229372 KB	Output is correct
38	Correct	696 ms	228064 KB	Output is correct
39	Correct	695 ms	228036 KB	Output is correct
40	Correct	752 ms	228076 KB	Output is correct
41	Correct	428 ms	227564 KB	Output is correct
42	Correct	487 ms	227704 KB	Output is correct
43	Correct	438 ms	228124 KB	Output is correct
44	Correct	379 ms	222680 KB	Output is correct
45	Correct	348 ms	222732 KB	Output is correct
46	Correct	362 ms	222776 KB	Output is correct
47	Correct	334 ms	222344 KB	Output is correct
48	Correct	341 ms	222840 KB	Output is correct
49	Correct	360 ms	222776 KB	Output is correct