Submission #604191

#	Time	Username	Problem	Language	Result	Execution time	Memory
604191		sofapuden	Distributing Candies (IOI21_candies)	C++17	100 / 100	1649 ms	48008 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct ST { 
	struct R {
		ll mn, mx;
		R() : mn(1ll<<60), mx(-(1ll<<60)) {}
		R(int x) : mn(x), mx(x) {}
	};

	int n;
	vector<R> st;
	vector<ll> lazy;

	ST(int sz) : n(sz), st(4*n,0), lazy(4*n,0) {}

	R mer(R a, R b){
		R c;
		c.mn = min(a.mn,b.mn);
		c.mx = max(a.mx,b.mx);
		return c;
	}

	void push(int p){
		st[p].mn+=lazy[p];
		st[p].mx+=lazy[p];
		if((p<<1|1) < 4*n){
			lazy[p<<1]+=lazy[p];
			lazy[p<<1|1]+=lazy[p];
		}
		lazy[p] = 0;
	}

	void update(int i, int j, ll v, int l, int r, int p){
		push(p);
		if(l >= i && r <= j){
			lazy[p]+=v;
			push(p);
			return;
		}
		if(l > j || r < i)return;
		int m = (l+r)>>1;
		update(i,j,v,l,m,p<<1);
		update(i,j,v,m+1,r,p<<1|1);
		st[p] = mer(st[p<<1],st[p<<1|1]);
	}

	R que(int i, int j, int l, int r, int p){
		push(p);
		if(l >= i && r <= j)return st[p];
		if(l > j || r < i)return R();
		int m = (l+r)>>1;
		return mer(que(i,j,l,m,p<<1), que(i,j,m+1,r,p<<1|1));
	}
};

struct T {
	ll x, i;
	T(int _x, int _i) : x(_x), i(_i) {}
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<vector<T>> am(n+1);
    for(int i = 0; i < q; ++i){
	    am[l[i]].emplace_back(v[i],i+1);
	    am[r[i]+1].emplace_back(-v[i],i+1);
    }
    ST S(q+1);

    vector<int> ans(n,0);

    for(int i = 0; i < n; ++i){
	    for(auto x : am[i]){
		    S.update(x.i,q,x.x,0,q,1);
	    }
	    ll a = -(1ll<<60), b = (1ll<<60);
	    int l = 0, r = q;
	    while(l <= r){
		    int m = (l+r) >> 1;
		    auto x = S.que(m,q,0,q,1);
		    if(x.mx-x.mn >= c[i]){
			    a = max(a,x.mn);
			    b = min(b,x.mx);
			    l = m+1;
		    }
		    else {
			    r = m-1;
		    }
	    }
	    auto x = S.que(l,q,0,q,1);
	    if(l == 0){
		    a = x.mn, b = c[i]-x.mn;
	    }
	    if(x.mn == a)ans[i] = (int)(S.que(q,q,0,q,1).mn-a);
	    else ans[i] = (int)(c[i] - (b - S.que(q,q,0,q,1).mn));
    }
    return ans;
}

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