MnZn过不了样例,求调qwq
查看原帖
MnZn过不了样例,求调qwq
758820
Porridge_Dust楼主2024/3/12 15:58
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 100;

typedef long long ll;

int k, n;
struct node {ll x1, x2, y, vis;} seg[N << 1];
ll b[N << 1], len;
ll sum[N << 4], lazy[N << 4];

bool cmp (const node &x, const node &y) {return x.y < y.y;}

int id (ll x) {return lower_bound(b + 1, b + len + 1, x) - b;}

inline int ls (int p) {return p << 1;}
inline int rs (int p) {return p << 1 | 1;}

void push_up (int p, int l, int r) {
	if (lazy[p] > 0) sum[p] = b[r + 1] - b[l];
	else sum[p] = sum[ls(p)] + sum[rs(p)];
}

void update (int p, int l, int r, int nl, int nr, int flag) {
	if (nl <= l && r <= nr) {lazy[p] += flag; push_up(p, l, r); return;}
	int mid = l + r >> 1;
	if (nl <= mid) update(ls(p), l, mid, nl, nr, flag);
	if (mid < nr) update(rs(p), mid + 1, r, nl, nr, flag);
	push_up(p, l, r);
}

int main () {
	cin >> k >> n;
	char op; ll X = 0, Y = 0;
	for (int i = 1, a; i <= n; i ++ ) {
		cin >> op >> a;
		if (op == 'N') seg[i * 2 - 1] = {X, X + k, Y, 1}, seg[i * 2] = {X, X + k, Y + a + k, -1}, Y += a, b[i * 2 - 1] = X, b[i * 2] = X + k;
		if (op == 'E') seg[i * 2 - 1] = {X, X + a + k, Y, 1}, seg[i * 2] = {X, X + a + k, Y + k, -1}, X += a, b[i * 2 - 1] = X, b[i * 2] = X + a + k;
		if (op == 'W') seg[i * 2 - 1] = {X - a, X + k, Y, 1}, seg[i * 2] = {X - a, X + k, Y + k, -1}, X -= a, b[i * 2 - 1] = X - a, b[i * 2] = X + k;
		if (op == 'S') seg[i * 2 - 1] = {X, X + k, Y - a, 1}, seg[i * 2] = {X, X + k, Y + k, -1}, Y -= a, b[i * 2 - 1] = X, b[i * 2] = X + k;
	}
	sort (seg + 1, seg + n * 2 + 1, cmp);
	sort (b + 1, b + n * 2 + 1);
	len = unique(b + 1, b + 2 * n + 1) - b - 1;
	
	ll ans = 0;
	for (int i = 1; i < n * 2; i ++ ) {
		update (1, 1, len - 1, id(seg[i].x1), id(seg[i].x2) - 1, seg[i].vis);
		ans += sum[1] * (seg[i + 1].y - seg[i].y);
	}
	cout << ans << '\n';
	
	return 0;
}
2024/3/12 15:58
加载中...