社区讨论

为什么POJ2484死活AC不了。。。

学术版参与者 4已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi86hefr
此快照首次捕获于
2025/11/21 09:25
4 个月前
此快照最后确认于
2025/11/21 09:25
4 个月前
查看原帖
RT,总是WA
我的程序:
CPP
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
LL n,w,h,a[maxn<<1],cnt;
struct  Data
{
	LL x,y1,y2,c;
	Data() { }
	Data(LL _x,LL _y1,LL _y2,LL _c):x(_x),y1(_y1),y2(_y2),c(_c) { }
}
li[maxn<<1];
inline bool operator<(const Data &a,const Data &b) { return a.x<b.x; }
#define Lc(o) (o<<1)
#define Rc(o) (o<<1|1)
LL mx[maxn<<3],tag[maxn<<3],pl,pr,upd;
inline void Add(int o,int v)
{
	tag[o]+=v;
	mx[o]+=v;
}
inline void PushDown(int o)
{
	Add(Lc(o),tag[o]);
	Add(Rc(o),tag[o]);
	tag[o]=0;
}
inline void PushUp(int o)
{
	mx[o]=max(mx[Lc(o)],mx[Rc(o)]);
}
void update(int o,int L,int R)
{
	if(pl<=L&&R<=pr) { Add(o,upd); return; }
	int M=(L+R)>>1;
	PushDown(o);
	if(pl<=M) update(Lc(o),L,M);
	if(pr>M) update(Rc(o),M+1,R);
	PushUp(o);
}
void solve()
{
	LL res=0,x,y,c;
	cnt=0;
	for(int i=0;i<n;i++)
	{
		cin>>x>>y>>c;
		li[i*2]=Data(x,y,y+h-1,c);
		li[i*2+1]=Data(x+w,y,y+h-1,-c);
		a[++cnt]=y; a[++cnt]=y+h-1;
	}
	sort(a+1,a+1+cnt);
	cnt=unique(a+1,a+1+cnt)-(a+1);
	sort(li,li+n*2);
	memset(mx,0,sizeof(mx)); memset(tag,0,sizeof(tag));
	for(int i=0;i<n*2;i++)
	{
		li[i].y1=lower_bound(a+1,a+1+cnt,li[i].y1)-a;
		li[i].y2=lower_bound(a+1,a+1+cnt,li[i].y2)-a;
		pl=li[i].y1; pr=li[i].y2; upd=li[i].c;
		update(1,1,cnt);
		res=max(res,mx[1]);
	}
	cout<<res<<endl;
}
int main()
{
	while(cin>>n>>w>>h) solve();
	return 0;
}
标程:
CPP
//Author:XuHt
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10006;
int n;
struct P {
	unsigned int x, y, z;
	int c;
	bool operator < (const P w) const {
		return x < w.x || (x == w.x && c < w.c);
	}
} a[N<<1];
unsigned int w, h, b[N<<1];
struct T {
	int l, r, ans, add;
} t[N<<3];

void build(int p, int l, int r) {
	t[p].l = l;
	t[p].r = r;
	t[p].ans = t[p].add = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

void spread(int p) {
	t[p<<1].add += t[p].add;
	t[p<<1].ans += t[p].add;
	t[p<<1|1].add += t[p].add;
	t[p<<1|1].ans += t[p].add;
	t[p].add = 0;
}

void change(int p, int l, int r, int c) {
	if (l <= t[p].l && r >= t[p].r) {
		t[p].add += c;
		t[p].ans += c;
		return;
	}
	if (t[p].add) spread(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) change(p<<1, l, r, c);
	if (r > mid) change(p<<1|1, l, r, c);
	t[p].ans = max(t[p<<1].ans, t[p<<1|1].ans);
}

void Stars_in_Your_Window() {
	for (int i = 1; i <= n; i++) {
		int k = i << 1;
		scanf("%u %u %d", &a[k-1].x, &a[k-1].y, &a[k-1].c);
		a[k].x = a[k-1].x + w;
		b[k-1] = a[k].y = a[k-1].y;
		b[k] = a[k].z = a[k-1].z = a[k].y + h - 1;
		a[k].c = -a[k-1].c;
	}
	n <<= 1;
	sort(b + 1, b + n + 1);
	int m = unique(b + 1, b + n + 1) - (b + 1);
	for (int i = 1; i <= n; i++) {
		a[i].y = lower_bound(b + 1, b + m + 1, a[i].y) - b;
		a[i].z = lower_bound(b + 1, b + m + 1, a[i].z) - b;
	}
	sort(a + 1, a + n + 1);
	build(1, 1, m);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		change(1, a[i].y, a[i].z, a[i].c);
		ans = max(ans, t[1].ans);
	}
	cout << ans << endl;
}

int main() {
	while (cin >> n >> w >> h) Stars_in_Your_Window();
	return 0;
}

回复

8 条回复,欢迎继续交流。

正在加载回复...