oj.uz

Submission #815175

# Submission time Handle Problem Language Result Execution time Memory
815175 2023-08-08T12:56:10 Z I_Love_EliskaM_ Distributing Candies (IOI21_candies) C++17
11 / 100
 106 ms 13944 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;

vector<int> p1(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size();
	vector<int> a(n,0);
	forn(i,q) {
		for (int j=l[i]; j<=r[i]; ++j) {
			a[j]=min(a[j]+v[i],c[j]);
			a[j]=max(a[j],0);
		}
	}
	return a;
}

vector<int> p2(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size();
	vector<ll> pr(n+1);
	forn(i,q) pr[l[i]]+=v[i], pr[r[i]+1]-=v[i];
	forn(i,n) pr[i+1]+=pr[i];
	vector<int> ans(n);
	forn(i,n) ans[i]=min(pr[i],1ll*c[i]);
	return ans;
}

#define int long long
struct sgt {
	vector<int> lazy, mn, mx, type;
	int sz=1;
	sgt(int n) {
		while (sz<n) sz<<=1;
		lazy.assign(4*sz,0);
		mn=mx=type=lazy;
	}
	void fix(int v, int t, int x) {
		if (v>=2*sz-1) return;
		if (type[v]==0) {
			type[v]=t, lazy[v]=x; return;
		}
		if (type[v]==1) {
			if (t==1) {
				lazy[v]+=x; return;
			}
			push(v);
			//fix(2*v+1,type[v],lazy[v]);
			//fix(2*v+2,type[v],lazy[v]);
			type[v]=t;
			lazy[v]=x;
		} else if (type[v]==2) {
			if (t==2) {
				return;
			}
			push(v);
			//fix(2*v+1,type[v],lazy[v]);
			//fix(2*v+2,type[v],lazy[v]);
			type[v]=t;
			lazy[v]=x;
		} else {
			if (t==3) {
				return;
			}
			push(v);
			//fix(2*v+1,type[v],lazy[v]);
			//fix(2*v+2,type[v],lazy[v]);
			type[v]=t;
			lazy[v]=x;
		}
	}
	void push(int v) {
		if (v>=2*sz-1) return;
		if (type[v]==1) {
			mn[v]+=lazy[v];
			mx[v]+=lazy[v];
			fix(2*v+1,type[v],lazy[v]);
			fix(2*v+2,type[v],lazy[v]);
		} else if (type[v]==2) {
			mn[v]=max(mn[v],lazy[v]);
			mx[v]=max(mx[v],lazy[v]);
			fix(2*v+1,type[v],lazy[v]);
			fix(2*v+2,type[v],lazy[v]);
		} else {
			mn[v]=min(mn[v],lazy[v]);
			mx[v]=min(mx[v],lazy[v]);
			fix(2*v+1,type[v],lazy[v]);
			fix(2*v+2,type[v],lazy[v]);
		}
		type[v]=0;
		lazy[v]=0;
	}

	void add(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			type[v]=1; lazy[v]=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		add(2*v+1,l,m,lx,rx,x);
		add(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void add(int l, int r, int x) {
		add(0,0,sz,l,r,x);
	}

	void maxx(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			type[v]=2; lazy[v]=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		maxx(2*v+1,l,m,lx,rx,x);
		maxx(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void maxx(int l, int r, int x) {
		maxx(0,0,sz,l,r,x);
	}

	void minn(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			type[v]=3; lazy[v]=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		minn(2*v+1,l,m,lx,rx,x);
		minn(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void minn(int l, int r, int x) {
		minn(0,0,sz,l,r,x);
	}

	void dfs(int v) {
		if (v>=2*sz-1) return;
		if (type[v]) push(v);
		dfs(2*v+1);
		dfs(2*v+2);
	}
};
#undef int

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size();
	if (max(n,q)<=2000) return p1(c,l,r,v);
	int z=1; forn(i,q) z&=v[i]>0;
	return p2(c,l,r,v);
	forn(i,n) if (c[i]!=c[0]) exit(0);

	#define int long long
	sgt st(n);
	forn(i,q) {
		st.add(l[i],r[i]+1,v[i]);
		if (v[i]>0) st.minn(l[i],r[i]+1,c[0]);
		else st.maxx(l[i],r[i]+1,0);
		//st.dfs(0);
		//forn(j,n) cout<<j<<": "<<st.mn[st.sz-1+j]<<' '<<st.mx[st.sz-1+j]<<'\n';
		//cout<<'\n';
	}
	st.dfs(0);
	vector<int32_t> ans;
	forn(i,n) assert(st.mn[st.sz-1+i]==st.mx[st.sz-1+i]);
	forn(i,n) ans.pb(st.mn[st.sz-1+i]);
	return ans;
	#undef int
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13944 KB Output is correct
2 Correct 84 ms 13932 KB Output is correct
3 Correct 106 ms 13804 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 66 ms 8264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 68 ms 7932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 90 ms 13944 KB Output is correct
7 Correct 84 ms 13932 KB Output is correct
8 Correct 106 ms 13804 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 66 ms 8264 KB Output isn't correct
11 Halted 0 ms 0 KB -