답안 #27305 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
27305	2017-07-12T07:35:04 Z	khsoo01	Dragon 2 (JOI17_dragon2)	C++11	60 / 100	3766 ms	262144 KB

dragon2

#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

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);
                          ^

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	41088 KB	Output is correct
2	Correct	29 ms	42532 KB	Output is correct
3	Correct	263 ms	57436 KB	Output is correct
4	Correct	613 ms	75924 KB	Output is correct
5	Correct	296 ms	53060 KB	Output is correct
6	Correct	9 ms	40904 KB	Output is correct
7	Correct	16 ms	40772 KB	Output is correct
8	Correct	9 ms	41000 KB	Output is correct
9	Correct	16 ms	41120 KB	Output is correct
10	Correct	13 ms	41004 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	45124 KB	Output is correct
2	Correct	436 ms	60576 KB	Output is correct
3	Correct	79 ms	45200 KB	Output is correct
4	Correct	33 ms	41564 KB	Output is correct
5	Correct	29 ms	41300 KB	Output is correct
6	Correct	86 ms	44956 KB	Output is correct
7	Correct	86 ms	44824 KB	Output is correct
8	Correct	79 ms	44824 KB	Output is correct
9	Correct	56 ms	44956 KB	Output is correct
10	Correct	63 ms	44956 KB	Output is correct

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	41088 KB	Output is correct
2	Correct	29 ms	42532 KB	Output is correct
3	Correct	263 ms	57436 KB	Output is correct
4	Correct	613 ms	75924 KB	Output is correct
5	Correct	296 ms	53060 KB	Output is correct
6	Correct	9 ms	40904 KB	Output is correct
7	Correct	16 ms	40772 KB	Output is correct
8	Correct	9 ms	41000 KB	Output is correct
9	Correct	16 ms	41120 KB	Output is correct
10	Correct	13 ms	41004 KB	Output is correct
11	Correct	99 ms	45124 KB	Output is correct
12	Correct	436 ms	60576 KB	Output is correct
13	Correct	79 ms	45200 KB	Output is correct
14	Correct	33 ms	41564 KB	Output is correct
15	Correct	29 ms	41300 KB	Output is correct
16	Correct	86 ms	44956 KB	Output is correct
17	Correct	86 ms	44824 KB	Output is correct
18	Correct	79 ms	44824 KB	Output is correct
19	Correct	56 ms	44956 KB	Output is correct
20	Correct	63 ms	44956 KB	Output is correct
21	Correct	83 ms	45132 KB	Output is correct
22	Correct	433 ms	60380 KB	Output is correct
23	Correct	3766 ms	195956 KB	Output is correct
24	Memory limit exceeded	396 ms	262144 KB	Memory limit exceeded
25	Halted	0 ms	0 KB	-

답안 #27305

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
0 / 40.0