Submission #767923

#	Time	Username	Problem	Language	Result	Execution time	Memory
767923		qwerasdfzxcl	Two Dishes (JOI19_dishes)	C++17	74 / 100	4266 ms	306180 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{
	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){
			treeB[i] = 1;
			return;
		}
 
		int m = (l+r)>>1;
		init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
	}
 
	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 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];
	}
 
	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;

struct Fenwick{
	ll a[1001000], tree[1001000];
	int sz;

	void update(int p, ll x){
		ll d = x - a[p];
		a[p] = x;
		while(p<=sz){
			tree[p] += d;
			p += p&-p;
		}
	}

	ll sum(int p){
		ll ret = 0;
		while(p){
			ret += tree[p];
			p ^= p&-p;
		}
		return ret;
	}
}treeV;
 
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(){
	treeV.sz = n+1;
	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);
		}

		treeV.update(i, W[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 + (treeV.sum(x) - treeV.sum(buf[idx].s)); // 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 += (treeV.sum(x) - treeV.sum(buf[idx].s)); // 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) + treeV.a[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);
	treeV.update(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){
	treeV.update(x, 0);
	refresh(x-1);
}
 
char FUCKYOU[100'000'000];
char *p = FUCKYOU;
#define SEX(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);

int main(){

	fread(FUCKYOU, 1, 100'000'000, stdin);
	SEX(n) SEX(m)
	for (int i=1;i<=n;i++){
		SEX(A[i]) SEX(S[i]) SEX(P[i]);
	}
	for (int i=1;i<=m;i++){
		SEX(B[i]) SEX(T[i]) SEX(Q[i]);
	}

	// 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));
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:228:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |  fread(FUCKYOU, 1, 100'000'000, stdin);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 17
• Subtask 8: 0 / 9