Submission #413927

#	Time	Username	Problem	Language	Result	Execution time	Memory
413927		amoo_safar	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	847 ms	214496 KiB

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 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40