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
// 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;
}
# 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
# 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
# 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