oj.uz

Submission #27277

# Submission time Handle Problem Language Result Execution time Memory
27277 2017-07-12T06:59:51 Z 김현수(#1143) Dragon 2 (JOI17_dragon2) C++14
60 / 100
 756 ms 262144 KB 
#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]; ll i;};
vector<data> rd[30005];

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

struct segtree {
	ll v[4444444], lim;
	void init () {
		for(lim=1;lim<=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) {
	if(XS > XE) {
		add(XS, s1, YS, YE, I);
		add(1, XE, YS, YE, I);
	}
	else if(YS > YE) {
		add(XS, XE, YS, s2, I);
		add(XS, XE, 1, YE, I);
	}
	else {
		swp[XE].push_back({YS, YE, 1, I});
		swp[XS-1].push_back({YS, YE, -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() < drg[B].size()) sadi(A, B, i);
			else majo(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(ll j=0;j<=s1;j++) swp[j].clear();
		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); k++;
			}
			for(auto &T : swp[j]) {
				ans[T.i] += seg.get(T.s, T.e) * T.x;
			}
		}
	}
	for(ll i=1;i<=q;i++) {
		mem[qry[i]] += ans[i];
		printf("%lld\n", mem[qry[i]]-1);
	}
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:152:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<drg[i].size();j++) {
               ^
dragon2.cpp:157:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(k < pt.size() && pt[k].X <= j) {
            ^
dragon2.cpp:127: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:130: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:133: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:136:27: 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 93816 KB Output is correct
2 Correct 59 ms 96880 KB Output is correct
3 Correct 403 ms 127552 KB Output is correct
4 Correct 756 ms 138396 KB Output is correct
5 Correct 339 ms 107900 KB Output is correct
6 Correct 23 ms 92988 KB Output is correct
7 Correct 23 ms 92988 KB Output is correct
8 Correct 19 ms 93244 KB Output is correct
9 Correct 19 ms 93680 KB Output is correct
10 Correct 19 ms 93560 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 104336 KB Output is correct
2 Correct 716 ms 146128 KB Output is correct
3 Correct 109 ms 100888 KB Output is correct
4 Correct 63 ms 93912 KB Output is correct
5 Correct 36 ms 93384 KB Output is correct
6 Correct 133 ms 103296 KB Output is correct
7 Correct 139 ms 103532 KB Output is correct
8 Correct 89 ms 98188 KB Output is correct
9 Correct 106 ms 102624 KB Output is correct
10 Correct 96 ms 102112 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 93816 KB Output is correct
2 Correct 59 ms 96880 KB Output is correct
3 Correct 403 ms 127552 KB Output is correct
4 Correct 756 ms 138396 KB Output is correct
5 Correct 339 ms 107900 KB Output is correct
6 Correct 23 ms 92988 KB Output is correct
7 Correct 23 ms 92988 KB Output is correct
8 Correct 19 ms 93244 KB Output is correct
9 Correct 19 ms 93680 KB Output is correct
10 Correct 19 ms 93560 KB Output is correct
11 Correct 139 ms 104336 KB Output is correct
12 Correct 716 ms 146128 KB Output is correct
13 Correct 109 ms 100888 KB Output is correct
14 Correct 63 ms 93912 KB Output is correct
15 Correct 36 ms 93384 KB Output is correct
16 Correct 133 ms 103296 KB Output is correct
17 Correct 139 ms 103532 KB Output is correct
18 Correct 89 ms 98188 KB Output is correct
19 Correct 106 ms 102624 KB Output is correct
20 Correct 96 ms 102112 KB Output is correct
21 Correct 159 ms 104344 KB Output is correct
22 Correct 679 ms 143196 KB Output is correct
23 Memory limit exceeded 113 ms 262144 KB Memory limit exceeded
24 Halted 0 ms 0 KB -