답안 #27282 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
27282	2017-07-12T07:03:32 Z	구사과(#1145)	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	2593 ms	11444 KB

dragon2

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #27282

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0