oj.uz

Submission #815191

# Submission time Handle Problem Language Result Execution time Memory
815191 2023-08-08T13:02:16 Z I_Love_EliskaM_ Distributing Candies (IOI21_candies) C++17
11 / 100
 5000 ms 22880 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;
}

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);
			type[v]=t;
			lazy[v]=x;
		} else if (type[v]==2) {
			if (t==2) {
				return;
			}
			push(v);
			type[v]=t;
			lazy[v]=x;
		} else {
			if (t==3) {
				return;
			}
			push(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);
	}
};

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

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 80 ms 11960 KB Output is correct
2 Correct 77 ms 12020 KB Output is correct
3 Correct 84 ms 12080 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 3640 ms 5148 KB Output is correct
3 Correct 3456 ms 19484 KB Output is correct
4 Execution timed out 5052 ms 22880 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 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 80 ms 11960 KB Output is correct
7 Correct 77 ms 12020 KB Output is correct
8 Correct 84 ms 12080 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3640 ms 5148 KB Output is correct
11 Correct 3456 ms 19484 KB Output is correct
12 Execution timed out 5052 ms 22880 KB Time limit exceeded
13 Halted 0 ms 0 KB -