Submission #485087

#	Time	Username	Problem	Language	Result	Execution time	Memory
485087		wwdd	Distributing Candies (IOI21_candies)	C++17	100 / 100	793 ms	37104 KiB

candies

#include "candies.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
// bruh
class ST {
	private:
		int n,h;
		vl sa,sb,lz;
		const ll STA = -1LL<<62;
		const ll STB = 1LL<<62;
		int log2(int v) {
			if(v <= 1) return 1;
			return log2(v/2)+1;
		}
		void ap(int p, ll val) {
			sa[p] += val;
			sb[p] += val;
			if(p < n) {lz[p] += val;}
		}
		void build(int p) {
			while(p > 1) {
				p >>= 1;
				if(p >= n) continue;
				sa[p] = max(sa[p<<1],sa[p<<1|1])+lz[p];
				sb[p] = min(sb[p<<1],sb[p<<1|1])+lz[p];
			}
		}
		void psh(int p) {
			for(int s=h;s>0;s--) {
				int i = p>>s;
				if(lz[i] != 0) {
					ap(i<<1,lz[i]);
					ap(i<<1|1,lz[i]);
					lz[i] = 0;
				}
			}
		}
	public:
		ST(int _n) {
			n = _n;
			h = log2(n);
			sa.assign(2*n,0);
			sb.assign(2*n,0);
			lz.assign(n,0);
		}
		void up(int l, int r, ll val) {
			if(l >= r) return;
			l += n;r += n;
			int li = l,ri = r;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {ap(l++,val);
				}
				if(r&1) {ap(--r,val);
				}
			}
			build(li);build(ri-1);
		}
		pl get(int l, int r) {
			l += n;r += n;
			psh(l);psh(r-1);
			ll ra = STA;
			ll rb = STB;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {
					ra = max(ra,sa[l]);
					rb = min(rb,sb[l]);
					l++;
				}
				if(r&1) {
					--r;
					ra = max(ra,sa[r]);
					rb = min(rb,sb[r]);
				}
			}
			return {ra,rb};
		}
};



std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
	l.insert(l.begin(),0);
	l.insert(l.begin(),0);
	r.insert(r.begin(),n-1);
	r.insert(r.begin(),n-1);
	v.insert(v.begin(),-(1e9+7));
	v.insert(v.begin(),1e9+7);
	ll q = l.size();
	ST st(q);
	vector<vector<pl> > ops(n+1);
	for(int i=0;i<q;i++) {
		ops[l[i]].emplace_back(i,v[i]);
		ops[r[i]+1].emplace_back(i,-v[i]);
	}
    std::vector<int> ans(n);
	for(int i=0;i<n;i++) {
		for(const auto& op: ops[i]) {
			st.up(op.first,q,op.second);
		}
		ll fv = st.get(q-1,q).first;
		ll sv = 0,ev = q-1;
		ll ls = 0;
		while(sv <= ev) {
			ll m = (sv+ev)/2;
			pl val = st.get(m,q);
			if(val.first-val.second > c[i]) {
				ls = m;
				sv = m+1;
			} else {
				ev = m-1;
			}
		}
		pl val = st.get(ls,q);
		ll los = st.get(ls,ls+1).first;
		if(los == val.first) {
			ans[i] = fv-val.second;
		} else {
			ans[i] = fv-val.first+c[i];
		}
	}
    return ans;
}

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