oj.uz

Submission #27280

# Submission time Handle Problem Language Result Execution time Memory
27280 2017-07-12T07:02:07 Z 구사과(#1145) Dragon 2 (JOI17_dragon2) C++14
45 / 100
 2583 ms 7856 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[30005], ans[30005];

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;
		}
		int ret = 0, qi = i;
		if(grp[x].size() < grp[y].size()){
			for(auto &i : grp[x]){
				add_sweep(0, edx[i.first] - 1, sty[i.second], edy[i.second] - 1, y, qi);
				add_sweep(stx[i.first], n-1, sty[i.second], edy[i.second] - 1, y, qi);
			}
		}
		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:113:7: warning: unused variable 'ret' [-Wunused-variable]
   int ret = 0, qi = i;
       ^
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4028 KB Output is correct
2 Correct 23 ms 4028 KB Output is correct
3 Correct 39 ms 4424 KB Output is correct
4 Runtime error 79 ms 7856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1386 ms 4428 KB Output is correct
2 Correct 2583 ms 4456 KB Output is correct
3 Correct 79 ms 4424 KB Output is correct
4 Correct 33 ms 4424 KB Output is correct
5 Correct 29 ms 4688 KB Output is correct
6 Correct 836 ms 4428 KB Output is correct
7 Correct 923 ms 4424 KB Output is correct
8 Correct 853 ms 4368 KB Output is correct
9 Correct 649 ms 4432 KB Output is correct
10 Correct 859 ms 4368 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4028 KB Output is correct
2 Correct 23 ms 4028 KB Output is correct
3 Correct 39 ms 4424 KB Output is correct
4 Runtime error 79 ms 7856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -