Submission #806864

#	Time	Username	Problem	Language	Result	Execution time	Memory
806864		sentheta	Distributing Candies (IOI21_candies)	C++17	27 / 100	875 ms	28956 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define DBG 0
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

const Int INF = 1e9+5;
const int N = 2e5+5;

int n, q;
V<int> c;
V<int> ql, qr, qv;


#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
// st.qry(t) = height at time t
struct St{
	Int mx[2*N], mn[2*N], lz[2*N];
	void upd(int l,int r,Int x,int v=0,int tl=0,int tr=q){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			mx[v] += x; mn[v] += x; lz[v] += x;
			return;
		}
		upd(l,r,x, lc,tl,mid);
		upd(l,r,x, rc,mid+1,tr);
		mx[v] = lz[v] + max(mx[lc], mx[rc]);
		mn[v] = lz[v] + min(mn[lc], mn[rc]);
	}
	Int qryMax(int l,int r=q,int v=0,int tl=0,int tr=q){
		if(r<tl || tr<l) return -INF*INF;
		if(l<=tl && tr<=r) return mx[v];
		return lz[v] + max({
			qryMax(l,r, lc,tl,mid), qryMax(l,r, rc,mid+1,tr)
		});
	}
	Int qryMin(int l,int r=q,int v=0,int tl=0,int tr=q){
		if(r<tl || tr<l) return INF*INF;
		if(l<=tl && tr<=r) return mn[v];
		return lz[v] + min({
			qryMin(l,r, lc,tl,mid), qryMin(l,r, rc,mid+1,tr)
		});
	}
} st;

// events
V<int> ev[N];

V<int> distribute_candies(V<int> _c,V<int> _ql,V<int> _qr,V<int> _qv){
	c.swap(_c); ql.swap(_ql); qr.swap(_qr); qv.swap(_qv);
	n = c.size();
	
	// dummy updates to guarantee both walls will be touched
	reverse(all(ql)); reverse(all(qr)); reverse(all(qv));
	ql.push_back(0); qr.push_back(n-1); qv.push_back(-INF);
	ql.push_back(0); qr.push_back(n-1); qv.push_back(+INF);
	reverse(all(ql)); reverse(all(qr)); reverse(all(qv));
	
	q = ql.size();
	
	// sort update events by l and r
	dbg(q);
	rep(i,0,q){
		cerr << ql[i] _ qr[i] _ qv[i] << nl;
		ev[ql[i]].push_back(i);
		ev[qr[i]+1].push_back(i);
	}
	cerr << nl;
	
	V<int> vans(n);
	rep(i,0,n){
		for(int e : ev[i]){
			// enable update
			if(ql[e]==i){
				st.upd(e,q, qv[e]);
			}
			// disable update
			else{
				st.upd(e,q, -qv[e]);
			}
			// rep(i,0,q) cerr << st.qryMax(i,i) << " ";
			// cerr << nl << nl;
		}
		
		// rep(i,0,q) cerr << st.qryMax(i,i) << " ";
		// cerr << nl << nl;
		
		// find last wall touch
		// if MAX-MIN>=c[i], that means in the future, we will touch another wall
		int t = 0;
		for(int J=1<<20; J; J/=2)
			if(t+J<q && st.qryMax(t+J)-st.qryMin(t+J)+1>=c[i]) t+=J;
		t++;
		
		dbg(t);
		dbg(st.qryMax(t));
		dbg(st.qryMin(t));
		dbg(st.qryMax(t)-st.qryMin(t));
		dbg(st.qryMax(t+1));
		dbg(st.qryMin(t+1));
		
		// find base wall and calculate ans
		Int ans;
		Int h = st.qryMax(q), base;
		// if last movement was UP, that means MAX is ceiling wall
		if(qv[t] > 0){
			base = st.qryMax(t) - c[i];
		}
		// if last movement was DOWN, that means MIN is floor/base wall
		else{
			base = st.qryMin(t);
		}
		// ans is relative height from base
		ans = h - base;
		vans[i] = ans;
		
		dbg(h);
		dbg(base);
		cerr << nl << nl;
		// if(i==1) return vans;
	}
	
	return vans;
	
}

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