Submission #27348

#	Time	Username	Problem	Language	Result	Execution time	Memory
27348		khsoo01	Dragon 2 (JOI17_dragon2)	C++11	100 / 100	1439 ms	245736 KiB

dragon2

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

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

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

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

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

struct segtree {
	ll 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);
}
ll ccw (const pii &A, const pii &B) {return 1ll*A.X*B.Y - 1ll*A.Y*B.X;}

bool isup (const pii &P) {
	return (0 < P.Y || (!P.Y && 0 < P.X));
}

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

void cpr (pll &P, vector<pll> &D, vector<data> &R, int O, vector<ll> &V, ll &S) {
	cp.clear(); V.clear();
	for(auto &T : D) cp.push_back(pii(T.X-P.X,T.Y-P.Y));
	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(), pii(T.X-P.X,T.Y-P.Y), cmp) - cp.begin() + 1);
	}
	for(auto &T : R) {
		bool flag = cmp(T.e[O], T.s[O]);
		T.s[O].X = lower_bound(cp.begin(), cp.end(), T.s[O], cmp) - cp.begin() + 1;
		T.e[O].X = upper_bound(cp.begin(), cp.end(), T.e[O], cmp) - cp.begin();
		if(flag != (T.e[O].X < T.s[O].X)) {T.s[O].X = -1; T.e[O].X = -1;}
	}
}

void add (ll XS, ll XE, ll YS, ll YE, ll I) {
	if(XS < 0 || YS < 0) return;
	swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
	if(XS > 1) 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);
}

data conv (pll S[], pll E[], ll I) {
	data C; C.i = I;
	C.s[0] = pii(S[0].X-p1.X, S[0].Y-p1.Y);
	C.e[0] = pii(E[0].X-p1.X, E[0].Y-p1.Y);
	C.s[1] = pii(S[1].X-p2.X, S[1].Y-p2.Y);
	C.e[1] = pii(E[1].X-p2.X, E[1].Y-p2.Y);
	return C;
}

void sadi (ll S, ll M, ll I) {
	for(auto &T : drg[S]) {
		pll L[2], R[2];
		L[0] = T; R[0] = Flip(p1, T);
		if(ccw(p1, L[0], p2) < 0) swap(L[0], R[0]);
		L[1] = T; R[1] = Flip(p2, T);
		if(ccw(p2, L[1], p1) < 0) swap(L[1], R[1]);
		rd[M].push_back(conv(L, R, I));
	}
}

void majo (ll S, ll M, ll I) {
	for(auto &T : drg[M]) {
		pll L[2], R[2];
		L[0] = p2; R[0] = Flip(p1, T);
		if(ccw(p1, L[0], R[0]) < 0) swap(L[0], R[0]);
		L[1] = p1; R[1] = Flip(p2, T);
		if(ccw(p2, L[1], R[1]) < 0) swap(L[1], R[1]);
		rd[S].push_back(conv(L, R, I));
	}
	for(auto &T : drg[M]) {
		pll L[2], R[2];
		L[0] = T; R[0] = Flip(p1, T);
		if(ccw(p1, L[0], p2) > 0) swap(L[0], R[0]);
		L[1] = T; R[1] = Flip(p2, T);
		if(ccw(p2, L[1], p1) > 0) swap(L[1], R[1]);
		rd[S].push_back(conv(L, R, I));
	}
}

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 'int main()':
dragon2.cpp:153:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<drg[i].size();j++) {
               ^
dragon2.cpp:158:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(k < pt.size() && pt[k].X <= j) {
            ^
dragon2.cpp:129: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:132: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:135: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:138:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^

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