답안 #23986 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23986	2017-05-28T14:52:44 Z	gs14004	Dragon 2 (JOI17_dragon2)	C++11	100 / 100	1719 ms	10656 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 query(int x, int y){
	if(mp.find(pi(x, y)) != mp.end()) return mp[pi(x, y)];
	int ret = 0;
	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)] = ret;
	return ret;
}

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);
	while(q--){
		int x, y;
		scanf("%d %d",&x,&y);
		printf("%d\n", query(x, y));
	}
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:89: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:91: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:93: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:100:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
dragon2.cpp:103: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	6 ms	3788 KB	Output is correct
2	Correct	13 ms	3788 KB	Output is correct
3	Correct	23 ms	4184 KB	Output is correct
4	Correct	183 ms	10124 KB	Output is correct
5	Correct	169 ms	10124 KB	Output is correct
6	Correct	3 ms	4052 KB	Output is correct
7	Correct	3 ms	4052 KB	Output is correct
8	Correct	6 ms	3788 KB	Output is correct
9	Correct	3 ms	3920 KB	Output is correct
10	Correct	9 ms	3788 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	419 ms	4188 KB	Output is correct
2	Correct	893 ms	4216 KB	Output is correct
3	Correct	46 ms	4184 KB	Output is correct
4	Correct	29 ms	4184 KB	Output is correct
5	Correct	36 ms	4448 KB	Output is correct
6	Correct	369 ms	4188 KB	Output is correct
7	Correct	379 ms	4184 KB	Output is correct
8	Correct	506 ms	4128 KB	Output is correct
9	Correct	423 ms	4192 KB	Output is correct
10	Correct	473 ms	4128 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3788 KB	Output is correct
2	Correct	13 ms	3788 KB	Output is correct
3	Correct	23 ms	4184 KB	Output is correct
4	Correct	183 ms	10124 KB	Output is correct
5	Correct	169 ms	10124 KB	Output is correct
6	Correct	3 ms	4052 KB	Output is correct
7	Correct	3 ms	4052 KB	Output is correct
8	Correct	6 ms	3788 KB	Output is correct
9	Correct	3 ms	3920 KB	Output is correct
10	Correct	9 ms	3788 KB	Output is correct
11	Correct	419 ms	4188 KB	Output is correct
12	Correct	893 ms	4216 KB	Output is correct
13	Correct	46 ms	4184 KB	Output is correct
14	Correct	29 ms	4184 KB	Output is correct
15	Correct	36 ms	4448 KB	Output is correct
16	Correct	369 ms	4188 KB	Output is correct
17	Correct	379 ms	4184 KB	Output is correct
18	Correct	506 ms	4128 KB	Output is correct
19	Correct	423 ms	4192 KB	Output is correct
20	Correct	473 ms	4128 KB	Output is correct
21	Correct	466 ms	4072 KB	Output is correct
22	Correct	993 ms	4240 KB	Output is correct
23	Correct	1183 ms	4580 KB	Output is correct
24	Correct	633 ms	10388 KB	Output is correct
25	Correct	223 ms	10520 KB	Output is correct
26	Correct	213 ms	10652 KB	Output is correct
27	Correct	36 ms	5636 KB	Output is correct
28	Correct	43 ms	5636 KB	Output is correct
29	Correct	1719 ms	10548 KB	Output is correct
30	Correct	219 ms	10548 KB	Output is correct
31	Correct	176 ms	10552 KB	Output is correct
32	Correct	196 ms	10652 KB	Output is correct
33	Correct	636 ms	10652 KB	Output is correct
34	Correct	243 ms	10652 KB	Output is correct
35	Correct	216 ms	10652 KB	Output is correct
36	Correct	249 ms	10652 KB	Output is correct
37	Correct	233 ms	10652 KB	Output is correct
38	Correct	949 ms	10652 KB	Output is correct
39	Correct	766 ms	10652 KB	Output is correct
40	Correct	613 ms	10652 KB	Output is correct
41	Correct	1426 ms	10552 KB	Output is correct
42	Correct	1139 ms	10532 KB	Output is correct
43	Correct	1073 ms	10656 KB	Output is correct
44	Correct	866 ms	5128 KB	Output is correct
45	Correct	516 ms	5180 KB	Output is correct
46	Correct	389 ms	5284 KB	Output is correct
47	Correct	499 ms	5128 KB	Output is correct
48	Correct	316 ms	5180 KB	Output is correct
49	Correct	216 ms	5280 KB	Output is correct

답안 #23986

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