D 求条 wa*1
  • 板块灌水区
  • 楼主Little_x_starTYJ
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/21 21:52
  • 上次更新2024/12/22 10:16:39
查看原帖
D 求条 wa*1
902351
Little_x_starTYJ楼主2024/12/21 21:52
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, sx, sy, ans;
map<int, int> mx, my;
int idx, idy;
vector<int> vx[200010], vy[200010];
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> sx >> sy;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		if (!mx[x]) {
			mx[x] = ++idx;
			vx[idx].push_back(y);
		} else {
			vx[mx[x]].push_back(y);
		}
		if (!my[y]) {
			my[y] = ++idy;
			vy[idy].push_back(x);
		} else {
			vy[my[y]].push_back(x);
		}
	}
	for (int i = 1; i <= idx; i++)
		sort(vx[i].begin(), vx[i].end());
	for (int i = 1; i <= idy; i++)
		sort(vy[i].begin(), vy[i].end());
	while (m--) {
		char c;
		int x;
		cin >> c >> x;
		if (c == 'L') {
			int xx = sx - x, yy = sy;
			if (my[yy]) {
				int k = lower_bound(vy[my[yy]].begin(), vy[my[yy]].end(), xx) - vy[my[yy]].begin();
				int kk = upper_bound(vy[my[yy]].begin(), vy[my[yy]].end(), sx) - vy[my[yy]].begin() - 1;
				if (kk >= k) {
					ans += kk - k + 1;
					for (int i = k; i <= kk; i++) {
//						int p = lower_bound(vx[vy[my[yy]][i]].begin(), vx[vy[my[yy]][i]].end(), xx) - vx[vy[my[yy]][i]].begin();
						vx[mx[vy[my[yy]][i]]].erase(lower_bound(vx[mx[vy[my[yy]][i]]].begin(), vx[mx[vy[my[yy]][i]]].end(), yy));
					}
					vy[my[yy]].erase(vy[my[yy]].begin() + k, vy[my[yy]].begin() + kk + 1);
				}
			}
			sx = xx, sy = yy;
		} else if (c == 'R') {
			int xx = sx + x, yy = sy;
			if (my[yy]) {
				int kk = upper_bound(vy[my[yy]].begin(), vy[my[yy]].end(), xx) - vy[my[yy]].begin() - 1;
				int k = lower_bound(vy[my[yy]].begin(), vy[my[yy]].end(), sx) - vy[my[yy]].begin();
				if (kk >= k) {
					ans += kk - k + 1;
					for (int i = k; i <= kk; i++) {
//						int p = lower_bound(vx[mx[vy[my[yy]][i]]].begin(), vx[mx[vy[my[yy]][i]]].end(), yy) - vx[mx[vy[my[yy]][i]]].begin();
//						cout << vy[my[yy]][i] << ' ' << yy << endl;
//						cout << vx[mx[vy[my[yy]][i]]][0] << endl;
						
						vx[mx[vy[my[yy]][i]]].erase(lower_bound(vx[mx[vy[my[yy]][i]]].begin(), vx[mx[vy[my[yy]][i]]].end(), yy));
					}
					vy[my[yy]].erase(vy[my[yy]].begin() + k, vy[my[yy]].begin() + kk + 1);
				}
			}
			sx = xx, sy = yy;
		} else if (c == 'U') {
			int xx = sx, yy = sy + x;
			if (mx[xx]) {
				int kk = upper_bound(vx[mx[xx]].begin(), vx[mx[xx]].end(), yy) - vx[mx[xx]].begin() - 1;
				int k = lower_bound(vx[mx[xx]].begin(), vx[mx[xx]].end(), sy) - vx[mx[xx]].begin();
				if (kk >= k) {
					ans += kk - k + 1;
					for (int i = k; i <= kk; i++) {
//						int p = lower_bound(vy[vx[mx[xx]][i]].begin(), vy[vx[mx[xx]][i]].end(), yy);
						vy[my[vx[mx[xx]][i]]].erase(lower_bound(vy[my[vx[mx[xx]][i]]].begin(), vy[my[vx[mx[xx]][i]]].end(), xx));
					}
					vx[mx[xx]].erase(vx[mx[xx]].begin() + k, vx[mx[xx]].begin() + kk + 1);
				}
			}
			sx = xx, sy = yy;
		} else {
			int xx = sx, yy = sy - x;
			if (my[yy]) {
				int k = lower_bound(vx[mx[xx]].begin(), vx[mx[xx]].end(), yy) - vx[mx[xx]].begin();
				int kk = upper_bound(vx[mx[xx]].begin(), vx[mx[xx]].end(), sy) - vx[mx[xx]].begin() - 1;
				if (kk >= k) {
					ans += kk - k + 1;
					for (int i = k; i <= kk; i++) {
//						int p = lower_bound(vy[vx[mx[xx]][i]].begin(), vy[vx[mx[xx]][i]].end(), yy);
						vy[my[vx[mx[xx]][i]]].erase(lower_bound(vy[my[vx[mx[xx]][i]]].begin(), vy[my[vx[mx[xx]][i]]].end(), xx));
					}
					vx[mx[xx]].erase(vx[mx[xx]].begin() + k, vx[mx[xx]].begin() + kk + 1);
				}
			}
			sx = xx, sy = yy;
		}
	}
	cout << sx << ' ' << sy << ' ' << ans;
	return 0;
}
2024/12/21 21:52
加载中...