Submission #767838

#	Time	Username	Problem	Language	Result	Execution time	Memory
767838		qwerasdfzxcl	Two Dishes (JOI19_dishes)	C++17	100 / 100	6034 ms	304192 KiB

dishes

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Block{
	int s, e;
	ll a0;

	Block(){}
	Block(int _s, int _e, ll _a0): s(_s), e(_e), a0(_a0) {}
};

vector<Block> buf;

struct Seg{
	ll treeV[2202000], V[1101000];
	int treeB[2202000];

	ll lazyBadd[2202000], lazyBidx[2202000];

	void init(int i, int l, int r, ll a[]){
		lazyBadd[i] = 0, lazyBidx[i] = -1;
		if (l==r){
			V[l] = a[l];
			treeV[i] = a[l];
			treeB[i] = 1;
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void propagate(int i, int l, int r){
		if (l==r){
			if (lazyBidx[i]!=-1) treeB[i] = lazyBidx[i];
			if (buf[treeB[i]].s==l) buf[treeB[i]].a0 += lazyBadd[i];
		}

		else{
			if (lazyBidx[i]!=-1){
				lazyBidx[i<<1] = lazyBidx[i];
				lazyBadd[i<<1] = 0;
				lazyBidx[i<<1|1] = lazyBidx[i];
				lazyBadd[i<<1|1] = 0;
			}

			lazyBadd[i<<1] += lazyBadd[i];
			lazyBadd[i<<1|1] += lazyBadd[i];
		}

		lazyBidx[i] = -1;
		lazyBadd[i] = 0;
	}

	void update(int i, int l, int r, int p, int v){
		// propagate(i, l, r);
		if (r<p || p<l) return;
		if (l==r){
			treeV[i] = v;
			V[l] = v;
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, p, v); update(i<<1|1, m+1, r, p, v);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void updateB(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazyBidx[i] = x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		updateB(i<<1, l, m, s, e, x); updateB(i<<1|1, m+1, r, s, e, x);
		// treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void add(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazyBadd[i] += x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		add(i<<1, l, m, s, e, x); add(i<<1|1, m+1, r, s, e, x);
		// treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	ll queryV(int i, int l, int r, int s, int e){
		// propagate(i, l, r);
		if (r<s || e<l) return 0;
		if (s<=l && r<=e) return treeV[i];

		int m = (l+r)>>1;
		return queryV(i<<1, l, m, s, e) + queryV(i<<1|1, m+1, r, s, e);
	}

	int queryB(int i, int l, int r, int p){
		propagate(i, l, r);
		if (r<p || p<l) return 0;
		if (l==r) return treeB[i];

		int m = (l+r)>>1;
		return queryB(i<<1, l, m, p) | queryB(i<<1|1, m+1, r, p);
	}
}tree;

int n, m;
ll A[1001000], B[1001000], S[1001000], T[1001000], P[1001000], Q[1001000];
ll sumA[1001000], sumB[1001000], W[1001000], mxA[1001000], mxB[1001000];
vector<int> Vp[1001000], Vm[1001000];

void init(){
	for (int i=1;i<=n;i++) sumA[i] = sumA[i-1] + A[i];
	for (int i=1;i<=m;i++) sumB[i] = sumB[i-1] + B[i];

	for (int i=1;i<=n;i++){
		mxB[i] = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1;
		
		if (mxB[i]==-1) W[i] = 0;
		else{
			W[i] = P[i];
			if (W[i] > 0) Vp[mxB[i]].push_back(i);
			else if (W[i] < 0) Vm[mxB[i]].push_back(i);
		}
	}
	for (int i=1;i<=m;i++){
		mxA[i] = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;
	}

	// printf("mxB: ");
	// for (int i=1;i<=n;i++) printf("%lld ", mxB[i]);
	// printf("\nmxA: ");
	// for (int i=1;i<=m;i++) printf("%lld ", mxA[i]);
	// printf("\nW: ");
	// for (int i=1;i<=n;i++) printf("%lld ", W[i]);
	// printf("\n");

	buf.emplace_back();
	buf.emplace_back(0, n, 0);
	tree.init(1, 0, n, W);
}


int getidx(int x){
	int ret = tree.queryB(1, 0, n, x);
	if (x > buf[ret].s) tree.queryB(1, 0, n, buf[ret].s);
	return ret;
}

ll calc(int x, int idx = -1){
	if (idx==-1) idx = getidx(x);
	return buf[idx].a0 + tree.queryV(1, 0, n, buf[idx].s+1, x);
}

void split(int x){
	int idx = getidx(x);
	
	if (buf[idx].s==x) return;

	buf.emplace_back(buf[idx].s, x-1, buf[idx].a0);
	buf[idx].a0 += tree.queryV(1, 0, n, buf[idx].s+1, x);
	buf[idx].s = x;

	tree.updateB(1, 0, n, buf.back().s, x-1, (int)buf.size()-1);
}

void merge(int cur, int nxt){
	buf[cur].e = buf[nxt].e;
	tree.updateB(1, 0, n, buf[nxt].s, buf[nxt].e, cur);
}

void refresh(int x){
	int cur = getidx(x);
	int re = buf[cur].e;

	while(true){
		if (re==n) break;
		
		int nxt = getidx(re+1);
		// printf("cur: (%d, %d, %lld) / nxt: (%d, %d, %lld) / w = %lld\n", buf[cur].s, buf[cur].e, buf[cur].a0, buf[nxt].s, buf[nxt].e, buf[nxt].a0, tree.queryV(1, 0, n, buf[cur].e+1, buf[cur].e+1));
		if (calc(re, cur) + tree.V[re+1] >= buf[nxt].a0) re = buf[nxt].e;
		else break;
	}

	tree.updateB(1, 0, n, buf[cur].e+1, re, cur);
	buf[cur].e = re;
}

void updateXp(int x, int w){ // between x-1 and x
	// printf("updateXp: %d\n", x);
	split(x);
	tree.update(1, 0, n, x, w);
}

void updateYp(int x, int q){
	// printf("updateYp: %d %d\n", x, q);
	tree.add(1, 0, n, 0, x, q);
	refresh(x);
}

void updateYm(int x, int q){
	if (x < n) split(x+1);
	tree.add(1, 0, n, 0, x, q);
}

void updateXm(int x){
	tree.update(1, 0, n, x, 0);
	refresh(x-1);
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i=1;i<=n;i++) cin >> A[i] >> S[i] >> P[i];
	for (int i=1;i<=m;i++) cin >> B[i] >> T[i] >> Q[i];

	init();

	for (int y=1;y<=m;y++){
		for (auto &x:Vp[y-1]) updateXp(x, 0);
		
		if (Q[y] > 0 && mxA[y] >= 0) updateYp(mxA[y], Q[y]);
		else if (Q[y] < 0 && mxA[y] >= 0) updateYm(mxA[y], Q[y]);

		for (auto &x:Vm[y-1]) updateXm(x);
		// for (int x=0;x<=n;x++) printf("%lld ", calc(x));
		// printf("\n");
	}

	printf("%lld\n", calc(n));
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9