oj.uz

Submission #413913

# Submission time Handle Problem Language Result Execution time Memory
413913 2021-05-29T17:12:41 Z amoo_safar Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 229564 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(true)
			A.Query_Att(x, y, i), B.Query_Att(x, y, i);
		else
			B.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 261 ms 215364 KB Output is correct
2 Correct 248 ms 215264 KB Output is correct
3 Correct 314 ms 215664 KB Output is correct
4 Correct 308 ms 220368 KB Output is correct
5 Correct 348 ms 221368 KB Output is correct
6 Correct 247 ms 216004 KB Output is correct
7 Correct 245 ms 215928 KB Output is correct
8 Correct 286 ms 215336 KB Output is correct
9 Correct 283 ms 215224 KB Output is correct
10 Correct 284 ms 215308 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 219744 KB Output is correct
2 Correct 384 ms 220164 KB Output is correct
3 Correct 340 ms 219948 KB Output is correct
4 Correct 334 ms 220520 KB Output is correct
5 Correct 335 ms 223692 KB Output is correct
6 Correct 355 ms 219216 KB Output is correct
7 Correct 337 ms 219336 KB Output is correct
8 Correct 338 ms 219212 KB Output is correct
9 Correct 300 ms 219124 KB Output is correct
10 Correct 356 ms 218992 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 215364 KB Output is correct
2 Correct 248 ms 215264 KB Output is correct
3 Correct 314 ms 215664 KB Output is correct
4 Correct 308 ms 220368 KB Output is correct
5 Correct 348 ms 221368 KB Output is correct
6 Correct 247 ms 216004 KB Output is correct
7 Correct 245 ms 215928 KB Output is correct
8 Correct 286 ms 215336 KB Output is correct
9 Correct 283 ms 215224 KB Output is correct
10 Correct 284 ms 215308 KB Output is correct
11 Correct 338 ms 219744 KB Output is correct
12 Correct 384 ms 220164 KB Output is correct
13 Correct 340 ms 219948 KB Output is correct
14 Correct 334 ms 220520 KB Output is correct
15 Correct 335 ms 223692 KB Output is correct
16 Correct 355 ms 219216 KB Output is correct
17 Correct 337 ms 219336 KB Output is correct
18 Correct 338 ms 219212 KB Output is correct
19 Correct 300 ms 219124 KB Output is correct
20 Correct 356 ms 218992 KB Output is correct
21 Correct 376 ms 219820 KB Output is correct
22 Correct 384 ms 220152 KB Output is correct
23 Correct 716 ms 220148 KB Output is correct
24 Correct 924 ms 225496 KB Output is correct
25 Correct 480 ms 227596 KB Output is correct
26 Correct 462 ms 229564 KB Output is correct
27 Correct 329 ms 226200 KB Output is correct
28 Correct 372 ms 226108 KB Output is correct
29 Execution timed out 4075 ms 225340 KB Time limit exceeded
30 Halted 0 ms 0 KB -