Submission #1232159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232159		a4n_	Distributing Candies (IOI21_candies)	C++20	0 / 100	832 ms	40952 KiB

candies

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}

struct Node {
    ll mn, mx, sum;
    Node() {
        mn = mx = sum = 0;
    }
} seg[2*N];

Node merge(Node a, Node b) {
    a.mn = min(a.mn, a.sum + b.mn);
    a.mx = max(a.mx, a.sum + b.mx);
    a.sum += b.sum;
    return a;
}
 
ll t, n, q, c[N];
vector<pll> Q[N];

void update(int ind, ll x) {
    seg[ind].sum += x;
    seg[ind].mn = min(0ll, seg[ind].sum);
    seg[ind].mx = max(0ll, seg[ind].sum);
    ind /= 2;
    while(ind > 0) {
        seg[ind] = merge(seg[2*ind], seg[2*ind + 1]); ind /= 2;
    }
}

Node query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
    if(l >= rc || lc >= r) return Node();
    if(lc >= l && rc <= r) return seg[ind];
    int mid = (lc + rc) / 2;
    return merge(query(l, r, 2*ind, lc, mid), query(l, r, 2*ind+1, mid, rc));
}

vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v) {
    n = size(_c), q = size(_l);
    for(int i=1; i<=n; i++) {
        c[i] = _c[i - 1];
    }

    for(int i=1; i<=q; i++) {
        Q[_l[i-1] + 1].pb({i, _v[i - 1]});
        Q[_r[i-1] + 2].pb({i, -_v[i - 1]});
        
    }

    vector<int> ans;
    for(int i=1; i<=n; i++) {
        for(auto it : Q[i]) {
            update(it.F + (1<<lg) - 1, it.S);
        }

        int l=0, r=q+1;
        while(r - l > 1) {
            int mid = (l + r) / 2;
            Node res = query(mid, q + 1);
            if(res.mx - res.mn >= c[i]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        Node n2 = query(l + 1, q + 1);
        // fuck(i);
        // fuck(r);
        if(seg[1].mx - seg[1].mn < c[i]) {
            ans.pb(seg[1].sum);
        } else if(_v[l - 1] < 0) {
            ans.pb(n2.sum);
        } else {
            ans.pb(c[i] + n2.sum);
            // fuck(n2.sum);
        }
    }

    return ans;
}

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