Submission #435902

#	Time	Username	Problem	Language	Result	Execution time	Memory
435902		rqi	Distributing Candies (IOI21_candies)	C++17	100 / 100	3918 ms	33984 KiB

candies

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

typedef long long ll;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define ins insert
#define bk back()
#define lb lower_bound

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a, b);
}

void ckmax(ll& a, ll b){
	a = max(a, b);
}

const ll INF = 1e18;
const int MOD = 1e9+7;

const int mx = 200005;
const int SZ = 262144;

pl mnmx[2*SZ];
ll lazy[2*SZ];

void pull(int ind){
	mnmx[ind] = mp(min(mnmx[2*ind].f, mnmx[2*ind+1].f), max(mnmx[2*ind].s, mnmx[2*ind+1].s));
}

void build(){
	for(int i = SZ-1; i >= 1; i--){
		pull(i);
	}
}

void push(int ind){
	mnmx[ind].f+=lazy[ind];
	mnmx[ind].s+=lazy[ind];
		
	if(2*ind+1 < 2*SZ){
		for(int i = 0; i < 2; i++){
			assert(2*ind+i < 2*SZ);
			lazy[2*ind+i]+=lazy[ind];
		}
	}
	

	lazy[ind] = 0;
}



void update(int l, int r, ll val, int ind = 1, int L = 0, int R = SZ-1){
	push(ind);
	if(l > R || r < L) return;
	if(l <= L && R <= r){
		lazy[ind]+=val;
		push(ind);
		return;
	}

	int M = (L+R)/2;

	update(l, r, val, 2*ind, L, M);
	update(l, r, val, 2*ind+1, M+1, R);

	pull(ind);
}

ll tot_sum = 0;

// int query(ll D, pl q_MNMX = mp(INF, -INF), int ind = 1, int L = 0, int R = SZ-1){ //return -1 if inconclusive
// 	push(ind);

// 	// if(D == 17 && R <= 9){
// 	// 	cout << "L, R: " << L << " " << R << " " << q_MNMX.f << " " << q_MNMX.s << "\n";
// 	// 	cout << mnmx[ind].f << " " << mnmx[ind].s << "\n";
// 	// }

// 	pl entire = mp(min(q_MNMX.f, mnmx[ind].f), max(q_MNMX.s, mnmx[ind].s));

// 	if(q_MNMX.s-q_MNMX.f >= D) return MOD;

// 	// if(L == 2 && R == 3){
// 	// 	cout << "entire: " << entire.f << " " << entire.s << "\n";
// 	// }
// 	if(entire.s-entire.f < D) return L;

// 	// if(L == 2 && R == 3){
// 	// 	cout << "entire: " << entire.f << " " << entire.s << "\n";
// 	// }
// 	if(L == R){
// 		return MOD;
// 	}

// 	int M = (L+R)/2;

	
// 	// cout << L << " " << R << " " << "querying second half" << "\n";
// 	int res = query(D, q_MNMX, 2*ind+1, M+1, R);
// 	if(res > M+1){
// 		return res;
// 	}

// 	assert(res == M+1);

// 	pl half = mp(min(q_MNMX.f, mnmx[2*ind+1].f), max(q_MNMX.s, mnmx[2*ind+1].s));
// 	int res2 = query(D, half, 2*ind, L, M);

// 	res = min(res, res2);

// 	// if(D == 17 && R <= 9){
// 	// 	cout << "L, R:" << L << " " << R << "\n";
// 	// 	cout << "res: " << res << "\n";
// 	// }
// 	return res;
// }

pl queryMnMx(int l, int r, int ind = 1, int L = 0, int R = SZ-1){
	push(ind);

	if(r < L || R < l) return mp(INF, -INF);

	if(l <= L && R <= r){
		return mnmx[ind];
	}

	int M = (L+R)/2;
	pl res1 = queryMnMx(l, r, 2*ind, L, M);
	pl res2 = queryMnMx(l, r, 2*ind+1, M+1, R);

	return mp(min(res1.f, res2.f), max(res1.s, res2.s));
}

int n, q;

int query(ll D){
	int lo = 0;
	int hi = q;
	while(lo < hi){
		int mid = (lo+hi)/2;

		bool works = 0;

		pl a = queryMnMx(mid, q);
		if(a.s-a.f < D){
			works = 1;
		}

		if(works){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}
	return lo;
}

vector<pair<int, ll>> updates[mx];

vi distribute_candies(vi c, vi l, vi r, vi v) {
    n = sz(c);
    q = sz(l);
    vi s(n, 0);

    for(int i = 0; i < q; i++){
    	updates[l[i]].pb(mp(i, v[i]));
    	updates[r[i]+1].pb(mp(i, -v[i]));
    }

    for(int i = q+1; i < SZ; i++){
    	mnmx[SZ+i] = mp(INF, -INF);
    }
    build();

    for(int i = 0; i < n; i++){
    	// cout << "i = " << i << "\n";
    	for(auto u: updates[i]){
    		update(u.f+1, q, u.s);
    	}

    	ll D = c[i];
    	ll tot = queryMnMx(q, q).f;

    	int pos = query(D);

    	// cout << D << " " << tot << " " << pos << "\n";
    	// cout.flush();


   		if(pos == 0){
   			pl a = queryMnMx(0, q);
   			s[i] = (int)(tot-a.f);
   		}
   		else{
   			// cout << "seg: ";
   			// for(int i = 0; i <= q; i++){
   			// 	pl a = queryMnMx(i, i);
   			// 	cout << a.f << " ";
   			// }
   			// cout << "\n";
   			// cout.flush();
   			pl a = queryMnMx(pos-1, q);
   			ll ext_val = queryMnMx(pos-1, pos-1).f;


   			// cout << a.f << " " << a.s << " " << ext_val << "\n";
   			// cout.flush();
   			if(ext_val == a.f){
   				s[i] = (int)(D-(a.s-tot));
   			}
   			else{
   				assert(ext_val == a.s);
   				s[i] = (int)(tot-a.f);
   			}
   		}
    }

    return s;
}

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