oj.uz

Submission #821840

# Submission time Handle Problem Language Result Execution time Memory
821840 2023-08-11T18:57:57 Z I_Love_EliskaM_ Distributing Candies (IOI21_candies) C++17
0 / 100
 1413 ms 45204 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;
#define pi pair<ll,ll>
#define f first
#define s second

#define int long long
const int inf=1e18;

struct sgt {
	vector<int> lazy;
	vector<pi> t;
	int sz=1;
	sgt(int n) {
		while (sz<n) sz<<=1;
		lazy.assign(4*sz,0);
		t.assign(2*sz,{0,0});
	}
	pi merge(pi a, pi b) {
		return {min(a.f,b.f), max(a.s,b.s)};
	}
	void push(int v) {
		t[v].f+=lazy[v];
		t[v].s+=lazy[v];
		lazy[2*v+1]+=lazy[v];
		lazy[2*v+2]+=lazy[v];
		lazy[v]=0;
	}
	void add(int v, int l, int r, int lx, int rx, int x) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			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);
		t[v]=merge(t[2*v+1],t[2*v+2]);
	}
	void add(int l, int r, int x) {
		add(0,0,sz,l,r,x);
	}
	pi query(int v, int l, int r, int lx, int rx) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return {inf,-inf};
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		auto lq=query(2*v+1,l,m,lx,rx);
		auto rq=query(2*v+2,m,r,lx,rx);
		t[v]=merge(t[2*v+1],t[2*v+2]);
		return merge(lq,rq);
	}
	pi query(int l, int r) {
		return query(0,0,sz,l,r);
	}
};

#undef int

void addqueries(int n, vector<int>&l, vector<int>&r, vector<int>&v) {
	reverse(all(l));
	reverse(all(r));
	reverse(all(v));
	forn(i,2) l.pb(0);
	forn(i,2) r.pb(n-1);
	v.pb(-1e9); v.pb(1e9);
	reverse(all(l));
	reverse(all(r));
	reverse(all(v));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size()+2;
	addqueries(n,l,r,v);

	vector<vector<int>> add(n), del(n);
	forn(i,q) add[l[i]].pb(i), del[r[i]].pb(i);

	sgt st(q);
	vector<int> ans(n);
	forn(i,n) {
		for(auto&x:add[i]) st.add(x,q,v[x]);

		int l=0, r=q-1;
		while (l<r) {
			int mid=(l+r)>>1;
			auto x = st.query(mid,q);
			if (x.s - x.f >= c[i]) l=mid+1;
			else r=mid;
		}
		auto x = st.query(r,r+1);
		auto y = st.query(q-1,q);
		assert(x.f==x.s);
		assert(y.f==y.s);
		if (r==q-1) {
			if (v[r]>0) {
				ans[i]=min(v[r],c[i]);
			} else {
				ans[i]=max(c[i]+v[r],0);
			}
			continue;
		}
		if (x.f>=y.s) {
			ans[i]=c[i]-x.f+y.f;
		} else {
			ans[i]=y.f-x.f;
		}

		for(auto&x:del[i]) st.add(x,q,-v[x]);
	}
	return ans;

}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1413 ms 45204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 292 KB Output isn't correct
2 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -