oj.uz

Submission #27282

# Submission time Handle Problem Language Result Execution time Memory
27282 2017-07-12T07:03:32 Z 구사과(#1145) Dragon 2 (JOI17_dragon2) C++14
100 / 100
 2593 ms 11444 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

struct pnt{
	int x, y, c;
	int r1, r2;
}a[30005], s, e;

lint ccw(pnt a, pnt b, pnt c){
	return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (c.x - a.x) * (b.y - a.y);
}

int n, m;
int stx[30005], sty[30005], edx[30005], edy[30005];

void label1(){
	sort(a, a+n, [&](const pnt &p, const pnt &q){
		bool bh1 = ccw(s, e, p) > 0;
		bool bh2 = ccw(s, e, q) > 0;
		if(bh1 != bh2) return bh1 > bh2;
		return ccw(s, p, q) > 0;
	});
	int dv = 0;
	for(int i=0; i<n; i++){
		a[i].r1 = i;
		if(ccw(s, e, a[i]) > 0) dv = i+1;
	}
	int p = 0;
	for(int i=dv; i<n; i++){
		while(p < dv && ccw(s, a[i], a[p]) > 0) p++;
		stx[i] = i;
		edx[i] = p;
	}
	p = dv;
	for(int i=0; i<dv; i++){
		while(p < n && ccw(s, a[i], a[p]) > 0) p++;
		stx[i] = p;
		edx[i] = i;
	}
}

void label2(){
	sort(a, a+n, [&](const pnt &p, const pnt &q){
		bool bh1 = ccw(s, e, p) > 0;
		bool bh2 = ccw(s, e, q) > 0;
		if(bh1 != bh2) return bh1 > bh2;
		return ccw(e, p, q) > 0;
	});
	int dv = 0;
	for(int i=0; i<n; i++){
		a[i].r2 = i;
		if(ccw(s, e, a[i]) > 0) dv = i+1;
	}
	int p = 0;
	for(int i=dv; i<n; i++){
		while(p < dv && ccw(e, a[i], a[p]) > 0) p++;
		sty[i] = p;
		edy[i] = i;
	}
	p = dv;
	for(int i=0; i<dv; i++){
		while(p < n && ccw(e, a[i], a[p]) > 0) p++;
		sty[i] = i;
		edy[i] = p;
	}
}

vector<pi> grp[30005];
map<pi, int> mp;
int refer[100005], ans[100005];

void add_sweep(int sx, int ex, int sy, int ey, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
	}
}

void add_sweep2(int y, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
	}
}

void add_sweep3(int x, int y, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
	}
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
	}
	scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
	label1();
	label2();
	for(int i=0; i<n; i++){
		grp[a[i].c].push_back(pi(a[i].r1, a[i].r2));
	}
	int q;
	scanf("%d",&q);
	for(int i=1; i<=q; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		if(mp.find(pi(x, y)) != mp.end()){
			refer[i] = mp[pi(x, y)];
			continue;
		}
		if(grp[x].size() < grp[y].size()){
			for(auto &j : grp[x]){
				add_sweep(0, edx[j.first] - 1, sty[j.second], edy[j.second] - 1, y, i);
				add_sweep(stx[j.first], n-1, sty[j.second], edy[j.second] - 1, y, i);
			}
		}
		else{
			for(auto &j : grp[y]){
				add_sweep2(j.second, x, i);
				add_sweep3(j.first, j.second, x, i);
			}
		}
		/*
		for(auto &i : grp[x]){
			for(auto &j : grp[y]){
				bool xma = !(edx[i.first] <= j.first && j.first < stx[i.first]);
				bool yma = (sty[i.second] <= j.second && j.second < edy[i.second]);
				if(xma && yma) ret++;
			}
		}*/
		mp[pi(x, y)] = i;
	}
	for(int i=1; i<=q; i++){
		if(refer[i]) printf("%d\n", ans[refer[i]]);
		else printf("%d\n", ans[i]);
	}
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:94:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
dragon2.cpp:96:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
                                            ^
dragon2.cpp:98:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
                                          ^
dragon2.cpp:105:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
dragon2.cpp:108:23: 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 4576 KB Output is correct
2 Correct 19 ms 4576 KB Output is correct
3 Correct 33 ms 4972 KB Output is correct
4 Correct 183 ms 10912 KB Output is correct
5 Correct 153 ms 10912 KB Output is correct
6 Correct 3 ms 4840 KB Output is correct
7 Correct 0 ms 4840 KB Output is correct
8 Correct 9 ms 4576 KB Output is correct
9 Correct 6 ms 4708 KB Output is correct
10 Correct 9 ms 4576 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 4976 KB Output is correct
2 Correct 2543 ms 5004 KB Output is correct
3 Correct 76 ms 4972 KB Output is correct
4 Correct 29 ms 4972 KB Output is correct
5 Correct 29 ms 5236 KB Output is correct
6 Correct 866 ms 4976 KB Output is correct
7 Correct 926 ms 4972 KB Output is correct
8 Correct 866 ms 4916 KB Output is correct
9 Correct 649 ms 4980 KB Output is correct
10 Correct 883 ms 4916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4576 KB Output is correct
2 Correct 19 ms 4576 KB Output is correct
3 Correct 33 ms 4972 KB Output is correct
4 Correct 183 ms 10912 KB Output is correct
5 Correct 153 ms 10912 KB Output is correct
6 Correct 3 ms 4840 KB Output is correct
7 Correct 0 ms 4840 KB Output is correct
8 Correct 9 ms 4576 KB Output is correct
9 Correct 6 ms 4708 KB Output is correct
10 Correct 9 ms 4576 KB Output is correct
11 Correct 1393 ms 4976 KB Output is correct
12 Correct 2543 ms 5004 KB Output is correct
13 Correct 76 ms 4972 KB Output is correct
14 Correct 29 ms 4972 KB Output is correct
15 Correct 29 ms 5236 KB Output is correct
16 Correct 866 ms 4976 KB Output is correct
17 Correct 926 ms 4972 KB Output is correct
18 Correct 866 ms 4916 KB Output is correct
19 Correct 649 ms 4980 KB Output is correct
20 Correct 883 ms 4916 KB Output is correct
21 Correct 1376 ms 4860 KB Output is correct
22 Correct 2593 ms 5028 KB Output is correct
23 Correct 2409 ms 5368 KB Output is correct
24 Correct 923 ms 11176 KB Output is correct
25 Correct 206 ms 11308 KB Output is correct
26 Correct 206 ms 11440 KB Output is correct
27 Correct 46 ms 6424 KB Output is correct
28 Correct 46 ms 6424 KB Output is correct
29 Correct 2109 ms 11336 KB Output is correct
30 Correct 256 ms 11336 KB Output is correct
31 Correct 196 ms 11340 KB Output is correct
32 Correct 269 ms 11440 KB Output is correct
33 Correct 933 ms 11440 KB Output is correct
34 Correct 206 ms 11440 KB Output is correct
35 Correct 199 ms 11440 KB Output is correct
36 Correct 209 ms 11440 KB Output is correct
37 Correct 189 ms 11440 KB Output is correct
38 Correct 1416 ms 11440 KB Output is correct
39 Correct 1156 ms 11440 KB Output is correct
40 Correct 979 ms 11440 KB Output is correct
41 Correct 2049 ms 11340 KB Output is correct
42 Correct 1593 ms 11320 KB Output is correct
43 Correct 1746 ms 11444 KB Output is correct
44 Correct 1759 ms 5916 KB Output is correct
45 Correct 743 ms 5968 KB Output is correct
46 Correct 543 ms 6072 KB Output is correct
47 Correct 593 ms 5916 KB Output is correct
48 Correct 436 ms 5968 KB Output is correct
49 Correct 339 ms 6068 KB Output is correct