Submission #132285

#	Time	Username	Problem	Language	Result	Execution time	Memory
132285		sebinkim	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1242 ms	14056 KiB

dragon2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

struct vec{
	ll x, y;
	
	vec() {}
	vec(ll x, ll y) : x(x), y(y) {}
	
	vec operator - (vec &v) { return vec(x - v.x, y - v.y); }
	ll operator * (vec &v) { return x * v.y - y * v.x; }
};

struct query{
	ll x, l, r, i;
	
	query() {}
	query(ll x, ll l, ll r, ll i) :
		x(x), l(l), r(r), i(i) {}
};

struct fenwick{
	ll T[101010];
	
	void addval(ll p, ll v) { for(; p<=1e5; p+=p&-p) T[p] += v; }
	ll getval(ll p) { return p? getval(p - (p & -p)) + T[p] : 0; }
	ll getval(ll l, ll r) { return getval(r) - getval(l - 1); }
};

fenwick T;
vector <pll> Q1[30303], Q2[30303];
vector <ll> G[30303], V;
vector <query> K;
vec P[30303];
ll X[101010], Y[101010], A[101010];
ll n, m, q;

void sort(ll f, ll *X)
{
	ll i;
	
	V.clear();
	
	if(!f) V.push_back(3), V.push_back(2);
	else V.push_back(1), V.push_back(0);
	
	for(i=4; i<n+n; i++){
		V.push_back(i);
	}
	
	vec vd = P[f] - P[f ^ 1];
	
	sort(V.begin() + 1, V.end(), [&](ll &a, ll &b){
		vec va = (a & 1? P[f] - P[a >> 1] : P[a >> 1] - P[f]);
		vec vb = (b & 1? P[f] - P[b >> 1] : P[b >> 1] - P[f]);
		bool fa = vd * va > 0;
		bool fb = vd * vb > 0;
		if(fa != fb) return fa;
		else return va * vb > 0;
	});
	
	for(i=0; i<V.size(); i++){
		X[V[i]] = i + 1;
	}
}

void solve(ll f, ll p)
{
	vector <pll> &Q = (!f? Q1[p] : Q2[p]);
	ll i, j;
	ll l11, l12, l21, l22, r11, r12, r21, r22;
	
	K.clear();
	sort(Q.begin(), Q.end());
	
	for(i=0; i<Q.size(); i=j){
		for(j=i; j<Q.size() && Q[i].first == Q[j].first; j++);
		for(ll &t: G[Q[i].first]){
			if(!f){
				tie(l11, r11) = minmax(X[t << 1], X[t << 1 | 1]);
				tie(l22, r22) = minmax(Y[t << 1], Y[t << 1 | 1]);
				K.emplace_back(l11 - 1, l22, r22, -Q[i].second);
				K.emplace_back(r11, l22, r22, Q[i].second);
			}
			else{
				if(X[t << 1] < X[t << 1 | 1]){
					l11 = X[3], r11 = X[t << 1];
					l12 = X[2], r12 = X[t << 1 | 1];
				}
				else{
					l11 = X[t << 1], r11 = n + n;
					l12 = X[t << 1 | 1], r12 = X[2];
				}
				
				if(Y[t << 1] < Y[t << 1 | 1]){
					l21 = Y[1], r21 = Y[t << 1];
					l22 = Y[0], r22 = Y[t << 1 | 1];
				}
				else{
					l21 = Y[t << 1], r21 = n + n;
					l22 = Y[t << 1 | 1], r22 = Y[0];
				}
				
				K.emplace_back(l11 - 1, l21, r21, -Q[i].second);
				K.emplace_back(r11, l21, r21, Q[i].second);
				K.emplace_back(l12 - 1, l22, r22, -Q[i].second);
				K.emplace_back(r12, l22, r22, Q[i].second);
			}
		}
	}
	
	sort(K.begin(), K.end(), [&](query &qa, query &qb){
		return qa.x < qb.x;
	});
	
	i = 0;
	
	for(query &t: K){
		for(; i<G[p].size() && X[G[p][i] << 1] <= t.x; i++){
			T.addval(Y[G[p][i] << 1], 1);
		}
		if(t.i > 0) A[t.i] += T.getval(t.l, t.r);
		else A[-t.i] -= T.getval(t.l, t.r);
	}
		
	for(; i--; ){
		T.addval(Y[G[p][i] << 1], -1);
	}
	
	for(i=0; i<Q.size(); i=j){
		for(j=i; j<Q.size() && Q[i].first == Q[j].first; j++){
			A[Q[j].second] = A[Q[i].second];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll i, a, b, c;
	
	cin >> n >> m; n += 2;
	
	for(i=2; i<n; i++){
		cin >> P[i].x >> P[i].y >> c;
		G[c].push_back(i);
	}
	
	cin >> P[0].x >> P[0].y >> P[1].x >> P[1].y;
	
	sort(0, X); sort(1, Y);
	
	cin >> q;
	
	for(i=1; i<=q; i++){
		cin >> a >> b;
		if(G[a].size() < G[b].size()) Q1[b].emplace_back(a, i);
		else Q2[a].emplace_back(b, i);
	}
	
	for(i=1; i<=m; i++){
		sort(G[i].begin(), G[i].end(), [&](ll &a, ll &b){
			return X[a << 1] < X[b << 1];
		});
		solve(0, i); solve(1, i);
	}
	
	for(i=1; i<=q; i++){
		cout << A[i] << endl;
	}
	
	return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'void sort(ll, ll*)':
dragon2.cpp:66:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++){
           ~^~~~~~~~~
dragon2.cpp: In function 'void solve(ll, ll)':
dragon2.cpp:80:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<Q.size(); i=j){
           ~^~~~~~~~~
dragon2.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i; j<Q.size() && Q[i].first == Q[j].first; j++);
            ~^~~~~~~~~
dragon2.cpp:123:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; i<G[p].size() && X[G[p][i] << 1] <= t.x; i++){
         ~^~~~~~~~~~~~
dragon2.cpp:134:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<Q.size(); i=j){
           ~^~~~~~~~~
dragon2.cpp:135:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i; j<Q.size() && Q[i].first == Q[j].first; j++){
            ~^~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40