Submission #27325

#	Time	Username	Problem	Language	Result	Execution time	Memory
27325		kdh9949	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4000 ms	33780 KiB

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;
		l = new Nod();
		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){
	return (b.x - a.x) * (c.y - b.y) > (c.x - b.x) * (b.y - a.y) ? 1 : -1;
}

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 (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:60: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:62: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:66: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:97: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 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40