社区讨论
为什么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 条回复,欢迎继续交流。
正在加载回复...