Submission #27298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
27298	2017-07-12T07:24:01 Z	김동현(#1138)	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4000 ms	33780 KB

dragon2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Pos{ ll x, y; int c; };

int n, m, k, sz[30010], vs[2];
Pos a[30010], p[2];
vector<Pos> v[2], pv[2][2], cv[2][30010], cpv[2][2][30010], tcv[30010];
function<bool(Pos, Pos)> cmp[2];

struct Nod{
	int v;
	Nod *l, *r;
	Nod() : v(0), l(nullptr), r(nullptr) {}
	void ini(int ns, int ne){
		if(ns == ne) return;
		if(l == nullptr) l = new Nod();
		if(r == nullptr) r = new Nod();
		int m = (ns + ne) / 2;
		l->ini(ns, m);
		r->ini(m + 1, ne);
	}
	Nod *upd(int x, int ns, int ne){
		if(x < ns || ne < x) return this;
		Nod *ret = new Nod();
		if(ns == ne){
			ret->v++;
			return ret;
		}
		int m = (ns + ne) / 2;
		ret->l = l->upd(x, ns, m);
		ret->r = r->upd(x, m + 1, ne);
		ret->v = ret->l->v + ret->r->v;
		return ret;
	}
	int get(int s, int e, int ns, int ne){
		if(ne < s || e < ns) return 0;
		if(s <= ns && ne <= e) return v;
		int m = (ns + ne) / 2;
		return l->get(s, e, ns, m) + r->get(s, e, m + 1, ne);
	}
};
Nod *tr[2][30010];
vector<int> lst[2][30010];

int ccw(Pos a, Pos b, Pos c){
	ll t = (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
	return t < 0 ? -1 : t > 0 ? 1 : 0;
}

int ud(Pos x){ return ccw(p[0], p[1], x) > 0 ? 0 : 1; }

int wh(const vector<Pos> &v, Pos x, int i){
	return int(lower_bound(v.begin(), v.end(), x, cmp[i]) - v.begin());
}

Pos trp(Pos p, Pos x){ return {2 * p.x - x.x, 2 * p.y - x.y}; }

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y, c; i <= n; i++){
		scanf("%d%d%d", &x, &y, &c);
		a[i] = {ll(x), ll(y), c};
		sz[c]++;
	}
	scanf("%lld%lld%lld%lld%d", &p[0].x, &p[0].y, &p[1].x, &p[1].y, &k);
	for(int i = 1; i <= n; i++){
		v[ud(a[i])].push_back(a[i]);
		cv[ud(a[i])][a[i].c].push_back(a[i]);
		tcv[a[i].c].push_back(a[i]);
	}
	cmp[0] = [](Pos a, Pos b){ return ccw(p[0], a, b) > 0; };
	cmp[1] = [](Pos a, Pos b){ return ccw(p[1], a, b) > 0; };
	for(int i = 0; i < 2; i++){
		vs[i] = v[i].size();
		for(int j = 0; j < 2; j++){
			pv[i][j] = v[j];
			sort(pv[i][j].begin(), pv[i][j].end(), cmp[i]);
			for(int t = 1; t <= m; t++){
				cpv[i][j][t] = cv[j][t];
				sort(cpv[i][j][t].begin(), cpv[i][j][t].end(), cmp[i]);
			}
		}
	}
	for(int i = 0; i < 2; i++){
		if(!vs[i]) continue;
		tr[i][0] = new Nod();
		tr[i][0]->ini(0, vs[i] - 1);
		for(int j = 1; j <= m; j++) lst[i][j].push_back(0);
		for(int j = 0; j < vs[i]; j++){
			Pos cur = pv[!i][i][j];
			tr[i][j + 1] = tr[i][lst[i][cur.c].back()]->upd(wh(pv[i][i], cur, i), 0, vs[i] - 1);
			lst[i][cur.c].push_back(j + 1);
		}
	}
	for(int x, y; k--; ){
		scanf("%d%d", &x, &y);
		int ans = 0;
		int fl = 0; if(sz[x] > sz[y]){ swap(x, y); fl = 1; }
		for(auto &i : tcv[x]){
			int d = ud(i);
			ans += int(cv[!d][y].size());
			auto t = lower_bound(cpv[d][!d][y].begin(), cpv[d][!d][y].end(), trp(p[d], i), cmp[d]);
			ans -= int(t - cpv[d][!d][y].begin());
			t = upper_bound(cpv[!d][!d][y].begin(), cpv[!d][!d][y].end(), trp(p[!d], i), cmp[!d]);
			ans -= int(cpv[!d][!d][y].end() - t);
			if(!vs[d]) continue;
			auto u = upper_bound(lst[d][y].begin(), lst[d][y].end(), wh(pv[!d][d], i, !d) + 1); u--;
			ans += tr[d][*u]->get(wh(pv[d][d], i, d), vs[d] - 1, 0, vs[d] - 1);
			if(!fl){
				ans += int(cv[d][y].size());
				t = lower_bound(cpv[!d][d][y].begin(), cpv[!d][d][y].end(), i, cmp[!d]);
				ans -= int(t - cpv[!d][d][y].begin());
				t = upper_bound(cpv[d][d][y].begin(), cpv[d][d][y].end(), i, cmp[d]);
				ans -= int(cpv[d][d][y].end() - t);
			}
		}
		printf("%d\n", ans);
	}
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:61:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
dragon2.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &c);
                              ^
dragon2.cpp:67:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%d", &p[0].x, &p[0].y, &p[1].x, &p[1].y, &k);
                                                                     ^
dragon2.cpp:98:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	11540 KB	Output is correct
2	Correct	19 ms	11596 KB	Output is correct
3	Correct	153 ms	11576 KB	Output is correct
4	Correct	299 ms	11688 KB	Output is correct
5	Correct	153 ms	11800 KB	Output is correct
6	Correct	13 ms	11732 KB	Output is correct
7	Correct	13 ms	11732 KB	Output is correct
8	Correct	9 ms	11548 KB	Output is correct
9	Correct	9 ms	11576 KB	Output is correct
10	Correct	13 ms	11564 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	139 ms	31740 KB	Output is correct
2	Correct	539 ms	32060 KB	Output is correct
3	Correct	136 ms	31944 KB	Output is correct
4	Correct	93 ms	31980 KB	Output is correct
5	Correct	139 ms	33780 KB	Output is correct
6	Correct	116 ms	31680 KB	Output is correct
7	Correct	126 ms	31680 KB	Output is correct
8	Correct	99 ms	30784 KB	Output is correct
9	Correct	69 ms	30744 KB	Output is correct
10	Correct	93 ms	30764 KB	Output is correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	11540 KB	Output is correct
2	Correct	19 ms	11596 KB	Output is correct
3	Correct	153 ms	11576 KB	Output is correct
4	Correct	299 ms	11688 KB	Output is correct
5	Correct	153 ms	11800 KB	Output is correct
6	Correct	13 ms	11732 KB	Output is correct
7	Correct	13 ms	11732 KB	Output is correct
8	Correct	9 ms	11548 KB	Output is correct
9	Correct	9 ms	11576 KB	Output is correct
10	Correct	13 ms	11564 KB	Output is correct
11	Correct	139 ms	31740 KB	Output is correct
12	Correct	539 ms	32060 KB	Output is correct
13	Correct	136 ms	31944 KB	Output is correct
14	Correct	93 ms	31980 KB	Output is correct
15	Correct	139 ms	33780 KB	Output is correct
16	Correct	116 ms	31680 KB	Output is correct
17	Correct	126 ms	31680 KB	Output is correct
18	Correct	99 ms	30784 KB	Output is correct
19	Correct	69 ms	30744 KB	Output is correct
20	Correct	93 ms	30764 KB	Output is correct
21	Correct	116 ms	31832 KB	Output is correct
22	Correct	526 ms	32020 KB	Output is correct
23	Correct	2929 ms	31932 KB	Output is correct
24	Execution timed out	4000 ms	31972 KB	Execution timed out
25	Halted	0 ms	0 KB	-