Submission #821879

#	Time	Username	Problem	Language	Result	Execution time	Memory
821879		TimDee	Distributing Candies (IOI21_candies)	C++17	100 / 100	3354 ms	41280 KiB

candies

#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);
	#define int long long

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

	sgt st(q);
	vector<int32_t> 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)>>1;
			auto x = st.query(mid,q);
			auto y = st.query(mid,mid+1);
			if (x.s - x.f < c[i]) r=mid-1;
			else l=mid;
		}
		assert(r<q-1);
		auto z = st.query(r,q);
		int t=r;
		l=r+1, r=q-1;
		while (l<r) {
			int mid=(l+r)>>1;
			auto x=st.query(t+1,mid+1);
			if (x.s!=z.s && x.f!=z.f) l=mid+1;
			else r=mid;
		}
		auto x = st.query(r,r+1);
		auto y = st.query(q-1,q);
		z = st.query(t,t+1);
		if (x.f <= z.f) ans[i]=y.f-x.f;
		else ans[i]=c[i]+y.f-x.f;		

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

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:96:9: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   96 |    auto y = st.query(mid,mid+1);
      |         ^

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33