oj.uz

Submission #127731

# Submission time Handle Problem Language Result Execution time Memory
127731 2019-07-10T04:11:38 Z 구재현(#3116) Dragon 2 (JOI17_dragon2) C++14
100 / 100
 1234 ms 167648 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];

struct sweep1{
	int pos, s, e, dx, idx;
	bool operator<(const sweep1 &c)const{
		return pos < c.pos;
	}
};

struct sweep2{
	int pos, idx;
	bool operator<(const sweep2 &c)const{
		return pos < c.pos;
	}
};

struct sweep3{
	int px, py, idx;
	bool operator<(const sweep3 &c)const{
		return pi(py, px) < pi(c.py, c.px);
	}
};

vector<sweep1> s1[30005];
vector<sweep2> s2[30005];
vector<sweep3> s3[30005];

void add_sweep(int sx, int ex, int sy, int ey, int gnum, int idx){
	if(sx > ex || sy > ey) return;
	s1[gnum].push_back({sx - 1, sy, ey, -1, idx});
	s1[gnum].push_back({ex, sy, ey, 1, idx});
}

void add_sweep2(int y, int gnum, int idx){
	s2[gnum].push_back({y, idx});
}

void add_sweep3(int x, int y, int gnum, int idx){
	s3[gnum].push_back({x, y, idx});
}

struct bit{
	int tree[30005];
	void add(int x, int v){
		x += 2;
		while(x <= n+2){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		x += 2;
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

struct sweep4{
	int x, y, dx;
	bool operator<(const sweep4 &c)const{
		return pi(y, x) < pi(c.y, c.x);
	}
};

void proc_sweep(int gnum){
	sort(s1[gnum].begin(), s1[gnum].end());
	sort(s2[gnum].begin(), s2[gnum].end());
	sort(s3[gnum].begin(), s3[gnum].end());
	sort(grp[gnum].begin(), grp[gnum].end());
	int p = 0;
	for(auto &i : s1[gnum]){
		while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
			bit.add(grp[gnum][p++].second, 1);
		}
		ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
	}
	while(p > 0){
		bit.add(grp[gnum][--p].second, -1);
	}
	vector<pi> vt;
	for(auto &i : grp[gnum]){
		vt.push_back(pi(sty[i.second], 1));
		vt.push_back(pi(edy[i.second], -1));
	}
	sort(vt.begin(), vt.end());
	int sum = 0;
	for(auto &i : s2[gnum]){
		while(p < vt.size() && vt[p].first <= i.pos){
			sum += vt[p++].second;
		}
		ans[i.idx] += sum;
	}
	vector<sweep4> vu;
	for(auto &i : grp[gnum]){
		vu.push_back({edx[i.first], sty[i.second], 1});
		vu.push_back({stx[i.first], sty[i.second], -1});
		vu.push_back({edx[i.first], edy[i.second], -1});
		vu.push_back({stx[i.first], edy[i.second], 1});
	}
	p = 0;
	sort(vu.begin(), vu.end());
	for(auto &i : s3[gnum]){
		while(p < vu.size() && vu[p].y <= i.py){
			bit.add(vu[p].x, vu[p].dx);
			p++;
		}
		ans[i.idx] -= bit.query(i.px);
	}
	while(p > 0){
		p--;
		bit.add(vu[p].x, -vu[p].dx);
	}
}

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);
			}
		}
		mp[pi(x, y)] = i;
	}
	for(int i=1; i<=m; i++) proc_sweep(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 'void proc_sweep(int)':
dragon2.cpp:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
         ~~^~~~~~~~~~~~~~~~~~
dragon2.cpp:164:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < vt.size() && vt[p].first <= i.pos){
         ~~^~~~~~~~~~~
dragon2.cpp:179:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < vu.size() && vu[p].y <= i.py){
         ~~^~~~~~~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
dragon2.cpp:194:8: 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:196:7: 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:203:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
dragon2.cpp:206:8: 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 10 ms 3656 KB Output is correct
2 Correct 13 ms 4344 KB Output is correct
3 Correct 60 ms 11896 KB Output is correct
4 Correct 190 ms 22520 KB Output is correct
5 Correct 161 ms 13944 KB Output is correct
6 Correct 9 ms 3704 KB Output is correct
7 Correct 9 ms 3576 KB Output is correct
8 Correct 9 ms 3680 KB Output is correct
9 Correct 7 ms 3576 KB Output is correct
10 Correct 8 ms 3636 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7264 KB Output is correct
2 Correct 101 ms 14036 KB Output is correct
3 Correct 60 ms 7456 KB Output is correct
4 Correct 46 ms 5624 KB Output is correct
5 Correct 45 ms 5752 KB Output is correct
6 Correct 42 ms 7268 KB Output is correct
7 Correct 45 ms 7272 KB Output is correct
8 Correct 55 ms 8116 KB Output is correct
9 Correct 41 ms 7104 KB Output is correct
10 Correct 40 ms 7072 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3656 KB Output is correct
2 Correct 13 ms 4344 KB Output is correct
3 Correct 60 ms 11896 KB Output is correct
4 Correct 190 ms 22520 KB Output is correct
5 Correct 161 ms 13944 KB Output is correct
6 Correct 9 ms 3704 KB Output is correct
7 Correct 9 ms 3576 KB Output is correct
8 Correct 9 ms 3680 KB Output is correct
9 Correct 7 ms 3576 KB Output is correct
10 Correct 8 ms 3636 KB Output is correct
11 Correct 58 ms 7264 KB Output is correct
12 Correct 101 ms 14036 KB Output is correct
13 Correct 60 ms 7456 KB Output is correct
14 Correct 46 ms 5624 KB Output is correct
15 Correct 45 ms 5752 KB Output is correct
16 Correct 42 ms 7268 KB Output is correct
17 Correct 45 ms 7272 KB Output is correct
18 Correct 55 ms 8116 KB Output is correct
19 Correct 41 ms 7104 KB Output is correct
20 Correct 40 ms 7072 KB Output is correct
21 Correct 58 ms 7312 KB Output is correct
22 Correct 105 ms 14100 KB Output is correct
23 Correct 577 ms 93648 KB Output is correct
24 Correct 1234 ms 167648 KB Output is correct
25 Correct 320 ms 26456 KB Output is correct
26 Correct 205 ms 16288 KB Output is correct
27 Correct 59 ms 8184 KB Output is correct
28 Correct 58 ms 8184 KB Output is correct
29 Correct 185 ms 16712 KB Output is correct
30 Correct 185 ms 15060 KB Output is correct
31 Correct 184 ms 14836 KB Output is correct
32 Correct 206 ms 16516 KB Output is correct
33 Correct 737 ms 90768 KB Output is correct
34 Correct 225 ms 14660 KB Output is correct
35 Correct 186 ms 14968 KB Output is correct
36 Correct 207 ms 16248 KB Output is correct
37 Correct 210 ms 16240 KB Output is correct
38 Correct 709 ms 87072 KB Output is correct
39 Correct 773 ms 98592 KB Output is correct
40 Correct 743 ms 93716 KB Output is correct
41 Correct 208 ms 16908 KB Output is correct
42 Correct 215 ms 18708 KB Output is correct
43 Correct 263 ms 22440 KB Output is correct
44 Correct 66 ms 7924 KB Output is correct
45 Correct 65 ms 7748 KB Output is correct
46 Correct 64 ms 7660 KB Output is correct
47 Correct 67 ms 9612 KB Output is correct
48 Correct 69 ms 8688 KB Output is correct
49 Correct 70 ms 8648 KB Output is correct