Submission #27305

#TimeUsernameProblemLanguageResultExecution timeMemory
27305khsoo01Dragon 2 (JOI17_dragon2)C++11
60 / 100
3766 ms262144 KiB
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll n, m, q, s1, s2, ans[100005];
pll p1, p2, qry[100005], piv;

map<pll, ll> mem;
vector<ll> z1, z2;
vector<pll> drg[30005], cp, pt;

struct data {pll s[2], e[2]; int i;};
vector<data> rd[30005];

struct sweep {int s, e, x, i;};
vector<sweep> swp[1111111];

struct segtree {
	int v[2222222], lim;
	void init () {
		for(lim=1;lim<=2*s2;lim<<=1);
		for(ll i=2*lim;--i;) v[i] = 0;
	}
	void upd (ll P, ll V) {
		P += lim;
		while(P) {v[P] += V; P >>= 1;}
	}
	ll get (ll S, ll E) {
		S += lim; E += lim;
		ll ret = 0;
		while(S <= E) {
			if(S%2==1) ret += v[S++];
			if(E%2==0) ret += v[E--];
			S >>= 1; E >>= 1;
		}
		return ret;
	}
} seg;

ll ccw (const pll &A, const pll &B, const pll &C) {
	return (A.X*B.Y+B.X*C.Y+C.X*A.Y) - (A.Y*B.X+B.Y*C.X+C.Y*A.X);
}

bool isup (const pll &A, const pll &B) {
	return (A.Y < B.Y || (A.Y == B.Y && A.X < B.X));
}

bool cmp (const pll &A, const pll &B) {
	bool F1 = isup(piv, A), F2 = isup(piv, B);
	if(F1 != F2) return F1;
	return ccw(piv, A, B) > 0;
}

void cpr (pll &P, vector<pll> &D, vector<data> &R, int O, vector<ll> &V, ll &S) {
	cp.clear(); V.clear(); piv = P;
	for(auto &T : D) cp.push_back(T);
	for(auto &T : R) {
		cp.push_back(T.s[O]);
		cp.push_back(T.e[O]);
	}
	sort(cp.begin(), cp.end(), cmp);
	cp.erase(unique(cp.begin(), cp.end()), cp.end());
	S = cp.size();
	for(auto &T : D) {
		V.push_back(lower_bound(cp.begin(), cp.end(), T, cmp) - cp.begin() + 1);
	}
	for(auto &T : R) {
		T.s[O].X = lower_bound(cp.begin(), cp.end(), T.s[O], cmp) - cp.begin() + 1;
		T.e[O].X = lower_bound(cp.begin(), cp.end(), T.e[O], cmp) - cp.begin() + 1;
	}
}

void add (ll XS, ll XE, ll YS, ll YE, ll I) {
	swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
	swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
	if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
}

pll Flip (const pll &A, const pll &B) {
	return pll(2*A.X - B.X, 2*A.Y - B.Y);
}

void sadi (ll S, ll M, ll I) {
	for(auto &T : drg[S]) {
		data C; C.i = I;
		C.s[0] = T; C.e[0] = Flip(p1, T);
		if(ccw(p1, C.s[0], p2) < 0) swap(C.s[0], C.e[0]);
		C.s[1] = T; C.e[1] = Flip(p2, T);
		if(ccw(p2, C.s[1], p1) < 0) swap(C.s[1], C.e[1]);
		rd[M].push_back(C);
	}
}

void majo (ll S, ll M, ll I) {
	for(auto &T : drg[M]) {
		data C; C.i = I;
		C.s[0] = p2; C.e[0] = Flip(p1, T);
		if(ccw(p1, C.s[0], C.e[0]) < 0) swap(C.s[0], C.e[0]);
		C.s[1] = p1; C.e[1] = Flip(p2, T);
		if(ccw(p2, C.s[1], C.e[1]) < 0) swap(C.s[1], C.e[1]);
		rd[S].push_back(C);
	}
	for(auto &T : drg[M]) {
		data C; C.i = I;
		C.s[0] = T; C.e[0] = Flip(p1, T);
		if(ccw(p1, C.s[0], p2) > 0) swap(C.s[0], C.e[0]);
		C.s[1] = T; C.e[1] = Flip(p2, T);
		if(ccw(p2, C.s[1], p1) > 0) swap(C.s[1], C.e[1]);
		rd[S].push_back(C);
	}
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) {
		ll A, B, C;
		scanf("%lld%lld%lld",&A,&B,&C);
		drg[C].push_back(pll(A, B));
	}
	scanf("%lld%lld%lld%lld%lld",&p1.X,&p1.Y,&p2.X,&p2.Y,&q);
	for(ll i=1;i<=q;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		qry[i] = pll(A, B);
		if(!mem[qry[i]]) {
			mem[qry[i]] = 1;
			if(drg[A].size() > 2*drg[B].size()) majo(A, B, i);
			else sadi(A, B, i);
		}
	}
	for(ll i=1;i<=m;i++) {
		cpr(p1, drg[i], rd[i], 0, z1, s1);
		cpr(p2, drg[i], rd[i], 1, z2, s2);
		for(auto &T : rd[i]) {
			add(T.s[0].X, T.e[0].X, T.s[1].X, T.e[1].X, T.i);
		}
		seg.init(); pt.clear();
		for(ll j=0;j<drg[i].size();j++) {
			pt.push_back(pll(z1[j], z2[j]));
		}
		sort(pt.begin(), pt.end());
		for(ll j=1,k=0;j<=s1;j++) {
			while(k < pt.size() && pt[k].X <= j) {
				seg.upd(pt[k].Y, 1);
				seg.upd(pt[k].Y+s2, 1);
				k++;
			}
			for(auto &T : swp[j]) {
				ans[T.i] += seg.get(T.s, T.e) * T.x;
			}
			swp[j].clear();
		}
	}
	for(ll i=1;i<=q;i++) {
		mem[qry[i]] += ans[i];
		printf("%lld\n", mem[qry[i]]-1);
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'void add(ll, ll, ll, ll, ll)':
dragon2.cpp:77:45: warning: narrowing conversion of 'YS' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
                                             ^
dragon2.cpp:77:27: warning: narrowing conversion of '(((YS > YE) * s2) + YE)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
                           ^
dragon2.cpp:77:45: warning: narrowing conversion of 'I' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
                                             ^
dragon2.cpp:78:48: warning: narrowing conversion of 'YS' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
                                                ^
dragon2.cpp:78:29: warning: narrowing conversion of '(((YS > YE) * s2) + YE)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
                             ^
dragon2.cpp:78:48: warning: narrowing conversion of 'I' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
                                                ^
dragon2.cpp:79:57: warning: narrowing conversion of 'YS' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
                                                         ^
dragon2.cpp:79:39: warning: narrowing conversion of '(((YS > YE) * s2) + YE)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
                                       ^
dragon2.cpp:79:57: warning: narrowing conversion of 'I' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
                                                         ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:142:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<drg[i].size();j++) {
               ^
dragon2.cpp:147:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(k < pt.size() && pt[k].X <= j) {
            ^
dragon2.cpp:118:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
dragon2.cpp:121:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&A,&B,&C);
                                 ^
dragon2.cpp:124:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld",&p1.X,&p1.Y,&p2.X,&p2.Y,&q);
                                                          ^
dragon2.cpp:127:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...