为什么44点WA了啊
查看原帖
为什么44点WA了啊
638148
liujiaxi123456楼主2023/1/16 11:46
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

namespace ljx_9420yy {

	const int maxn = 3e5+5, inf = 2e6;
	int Q, x, r, ans[maxn];
	char op;

	struct Que {
		int l, len, r;
	} que[maxn];

	struct Seg {
		int wait, sum;
	} seg[inf*4];
	
	void build(int x, int l, int r){
		if(l == r){
			seg[x].wait = l;
			return ;
		}
		int mid = (l+r)>>1;
		build(x<<1, l, mid);
		build(x<<1|1, mid+1, r);
		seg[x].wait = seg[x<<1|1].wait;
	}

	void modify(int x, int l, int r, int i, int op) {
		if(r<i || i<l)	return ;
		if(l == r) {
			seg[x].sum += op;
			seg[x].wait += op;
			return ;
		}
		int mid = (l+r)>>1;
		modify(x<<1, l, mid, i, op);
		modify(x<<1|1, mid+1, r, i, op);
		seg[x].sum = seg[x<<1].sum + seg[x<<1|1].sum;
		seg[x].wait = max(seg[x<<1].wait+seg[x<<1|1].sum, seg[x<<1|1].wait);	//若左边往右边挤后中间还有空,那一定取右边 
	}

	void Query(int x, int l, int r, int L, int R) {
		if(r<L || R<l)	return ;
		if(L<=l && r<=R) {
			ans[ans[0]] = max(ans[ans[0]]+seg[x].sum, seg[x].wait);	//ans一定是左边的wait 
			return ;
		}
		int mid = (l+r)>>1;
		Query(x<<1, l, mid, L, R);
		Query(x<<1|1, mid+1, r, L, R);
		return ;
	}

	int main() {
		cin>> Q;
		build(1, 1, inf);
		for(int i=1; i<=Q; i++) {
			cin>> op;
			if(op == '+'){
				scanf("%d%d", &que[i].l, &que[i].len);
//				printf("modify:%d, %d\n\n", que[i].l, que[i].len);
				modify(1, 1, inf, que[i].l, que[i].len);
			}
			else if(op == '-')	scanf("%d", &x), modify(1, 1, inf, que[x].l, -que[x].len);
			else	scanf("%d", &r), ++ans[0], Query(1, 1, inf, 1, r), ans[ans[0]] -= r;
//			cout<< "Query"<< ans[ans[0]]+r<< "\n\n";
//			cout<< "       "<< seg[1].wait << "\n";
//			cout<< "   "<< seg[2].wait<< "       "<< seg[3].wait<< "\n";
//			cout<< " "; for(int i=4; i<=7; i++)	cout<< seg[i].wait<< "   "; cout<< "\n";
//			for(int i=8; i<=15; i++)	cout<< seg[i].wait<< " "; cout<< "\n";
		}
		for(int i=1; i<=ans[0]; i++)	printf("%d\n", ans[i]);
		return 0;
	}

}
int main() {
//	freopen("P1908_6.in", "r", stdin);
//	freopen("P1908_6.out", "w", stdout);
	ljx_9420yy::main();
	return 0;
}
2023/1/16 11:46
加载中...