【线段树 扫描线】2021牛客暑期多校训练营6 H Hopping Rabbit
2021-09-07 21:37:00 # ACM

题链

题目解析

由于兔子一跳能跳 m 个单位，可以将所有陷阱映射到 [0,m−1] 的矩阵内，当然映射很麻烦，补过的题现在看代码已经看不懂怎么映射的了…

映射完后对以扫描线的形式遍历每一个 y 值，如果这个 y 值某处的 x 点未被覆盖，那么这个点就是答案；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 998244353
	#define MAXN 1e18
	#define MS 200005

int n,m;
struct node{
	int cnt;
	int la;
}p[MS<<2];
struct seg{
	int xl,xr,w;
};
vector<seg > vc[MS<<2];
int ansx,ansy;

void push_up(int rt){
	p[rt].cnt = min(p[ls].cnt, p[rs].cnt);
}

void push_down(int rt){
	if(p[rt].la){
		int t = p[rt].la;
		p[ls].cnt += t; p[rs].cnt += t;
		p[ls].la += t; p[rs].la += t;
		p[rt].la = 0;
	}
}

void update(int L,int R,int l,int r,int rt,int val){
	if(L <= l && r <= R){
		p[rt].cnt += val;
		p[rt].la += val;
		return; 
	}
	int m = l+r>>1;
	push_down(rt);
	if(m >= L) update(L,R,l,m,ls,val);
	if(m <  R) update(L,R,m+1,r,rs,val);
	push_up(rt);
}

int get(int l,int r,int rt){
	if(l == r) return l;
	int m = l+r>>1;
	push_down(rt);
	if(p[ls].cnt == 0) return get(l,m,ls);
	else if(p[rs].cnt == 0) return get(m+1,r,rs);
}

void cal(int x1, int y1, int x2, int y2){
	int lenx = max(abs(x2-0), abs(m-x1));
	int leny = max(abs(y2-0), abs(m-y1));
	if(lenx >= x2-x1+m || leny >= y2-y1+m) return;
	
	int cx = max(x1, 0);
	int cy = max(y1, 0);
	int dx = min(x2, m);
	int dy = min(y2, m);
	dx-- ,dy--;
	
	vc[cy].push_back({cx, dx, 1});
	vc[dy+1].push_back({cx, dx, -1});
}

void calc(int x1, int y1, int x2, int y2){
	int w = x2-x1, h = y2-y1;
	int x = (x1%m+m)%m;
	int y = (y1%m+m)%m;
	cal(x, y, x+w, y+h);
	cal(x-m, y, x+w-m, y+h);
	cal(x, y-m, x+w, y+h-m);
	cal(x-m, y-m, x+w-m, y+h-m);
}

void solve(){
	cin >> n >> m;;
	for(int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		calc(x1, y1, x2, y2);
	}
	int flag = 0;
	for(int i=0;i<m;i++){
		for(auto t:vc[i]){
			update(t.xl, t.xr, 0, m-1, 1, t.w);
		}
		if(p[1].cnt == 0){
			flag = 1;
			ansx = get(0,m-1,1);
			ansy = i;
			break;
		}
	}
	if(flag){
		cout << "YES\n";
		cout << ansx << " " << ansy << "\n";
	}
	else{
		cout << "NO\n";
	}
}

int main() {
//	ios::sync_with_stdio(false);
	int ce;
//	cin >> ce;
	ce = 1;
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/
Prev
2021-09-07 21:37:00 # ACM
Next