oj.uz

Submission #815187

# Submission time Handle Problem Language Result Execution time Memory
815187 2023-08-08T13:01:01 Z I_Love_EliskaM_ Distributing Candies (IOI21_candies) C++17
11 / 100
 5000 ms 42120 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<ll> a(n,0);
	forn(i,q) {
		for (int j=l[i]; j<=r[i]; ++j) {
			a[j]=min(a[j]+v[i],1ll*c[j]);
			a[j]=max(a[j],0ll);
		}
	}
	vector<int> ans(n);
	forn(i,n) ans[i]=a[i];
	return ans;
}

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;
	if (z) 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 0 ms 212 KB Output is correct
3 Correct 2 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 124 ms 12004 KB Output is correct
2 Correct 76 ms 11964 KB Output is correct
3 Correct 76 ms 12008 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 Correct 4660 ms 5272 KB Output is correct
3 Correct 4508 ms 36000 KB Output is correct
4 Execution timed out 5026 ms 42120 KB Time limit exceeded
5 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 41 ms 4960 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 0 ms 212 KB Output is correct
3 Correct 2 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 124 ms 12004 KB Output is correct
7 Correct 76 ms 11964 KB Output is correct
8 Correct 76 ms 12008 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4660 ms 5272 KB Output is correct
11 Correct 4508 ms 36000 KB Output is correct
12 Execution timed out 5026 ms 42120 KB Time limit exceeded
13 Halted 0 ms 0 KB -