답안 #413927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413927	2021-05-29T17:32:01 Z	amoo_safar	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	847 ms	214496 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<int, int> 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 1ll * A.F * B.S - 1ll * 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);

	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(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];
	}
	A.Solve();
	B.Solve();
	for(int i = 0; i < q; i++)
		cout << -ans[i] << '\n';
	return 0;
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	230 ms	202508 KB	Output is correct
2	Correct	211 ms	202532 KB	Output is correct
3	Correct	264 ms	202900 KB	Output is correct
4	Correct	273 ms	207432 KB	Output is correct
5	Correct	258 ms	207192 KB	Output is correct
6	Correct	213 ms	203284 KB	Output is correct
7	Correct	209 ms	203204 KB	Output is correct
8	Correct	248 ms	202732 KB	Output is correct
9	Correct	240 ms	202696 KB	Output is correct
10	Correct	233 ms	202604 KB	Output is correct

Subtask #2

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	295 ms	205208 KB	Output is correct
2	Correct	330 ms	205460 KB	Output is correct
3	Correct	280 ms	205184 KB	Output is correct
4	Correct	272 ms	205704 KB	Output is correct
5	Correct	321 ms	209844 KB	Output is correct
6	Correct	325 ms	204952 KB	Output is correct
7	Correct	297 ms	204976 KB	Output is correct
8	Correct	292 ms	204792 KB	Output is correct
9	Correct	273 ms	204912 KB	Output is correct
10	Correct	278 ms	204856 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	230 ms	202508 KB	Output is correct
2	Correct	211 ms	202532 KB	Output is correct
3	Correct	264 ms	202900 KB	Output is correct
4	Correct	273 ms	207432 KB	Output is correct
5	Correct	258 ms	207192 KB	Output is correct
6	Correct	213 ms	203284 KB	Output is correct
7	Correct	209 ms	203204 KB	Output is correct
8	Correct	248 ms	202732 KB	Output is correct
9	Correct	240 ms	202696 KB	Output is correct
10	Correct	233 ms	202604 KB	Output is correct
11	Correct	295 ms	205208 KB	Output is correct
12	Correct	330 ms	205460 KB	Output is correct
13	Correct	280 ms	205184 KB	Output is correct
14	Correct	272 ms	205704 KB	Output is correct
15	Correct	321 ms	209844 KB	Output is correct
16	Correct	325 ms	204952 KB	Output is correct
17	Correct	297 ms	204976 KB	Output is correct
18	Correct	292 ms	204792 KB	Output is correct
19	Correct	273 ms	204912 KB	Output is correct
20	Correct	278 ms	204856 KB	Output is correct
21	Correct	293 ms	205320 KB	Output is correct
22	Correct	336 ms	205396 KB	Output is correct
23	Correct	670 ms	205564 KB	Output is correct
24	Correct	847 ms	210340 KB	Output is correct
25	Correct	373 ms	212368 KB	Output is correct
26	Correct	415 ms	214496 KB	Output is correct
27	Correct	272 ms	212420 KB	Output is correct
28	Correct	286 ms	212392 KB	Output is correct
29	Correct	387 ms	212516 KB	Output is correct
30	Correct	363 ms	212452 KB	Output is correct
31	Correct	374 ms	212540 KB	Output is correct
32	Correct	373 ms	212696 KB	Output is correct
33	Correct	627 ms	212756 KB	Output is correct
34	Correct	330 ms	212676 KB	Output is correct
35	Correct	343 ms	213752 KB	Output is correct
36	Correct	375 ms	214240 KB	Output is correct
37	Correct	360 ms	214336 KB	Output is correct
38	Correct	704 ms	212868 KB	Output is correct
39	Correct	654 ms	212708 KB	Output is correct
40	Correct	624 ms	212940 KB	Output is correct
41	Correct	485 ms	212588 KB	Output is correct
42	Correct	411 ms	212572 KB	Output is correct
43	Correct	426 ms	212744 KB	Output is correct
44	Correct	316 ms	208252 KB	Output is correct
45	Correct	316 ms	208308 KB	Output is correct
46	Correct	362 ms	208380 KB	Output is correct
47	Correct	355 ms	208060 KB	Output is correct
48	Correct	320 ms	208504 KB	Output is correct
49	Correct	318 ms	208388 KB	Output is correct