Submission #1221492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221492		HappyCapybara	Distributing Candies (IOI21_candies)	C++17	0 / 100	4980 ms	64632 KiB

candies

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

#define ll long long

// total, max prefix, max loc, min prefix, min loc

vector<ll> dummy = {0, (ll)-pow(10, 18), -1, (ll)pow(10, 18), -1};

int q;
vector<vector<ll>> st;
vector<int> v;

void merge(vector<ll>& node, vector<ll> l, vector<ll> r){
    node[0] = l[0]+r[0];
    node[1] = max(l[1], r[1]+l[0]);
    node[2] = l[1] > r[1]+l[0] ? l[2] : r[2];
    node[3] = min(l[3], r[3]+l[0]);
    node[4] = l[3] < r[3]+l[0] ? l[4] : r[4];
}

void update(int pos, int val, int node=1, int tl=0, int tr=q-1){
    if (tl == tr){
        st[node][0] += val;
        st[node][1] = max(0ll, st[node][0]);
        st[node][2] = st[node][0] > 0 ? pos : pos-1;
        st[node][3] = min(0ll, st[node][0]);
        st[node][4] = st[node][0] < 0 ? pos : pos-1;
        return;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) update(pos, val, node*2, tl, tm);
    else update(pos, val, node*2+1, tm+1, tr);
    merge(st[node], st[node*2], st[node*2+1]);
}

vector<ll> query(int l, int r, int node=1, int tl=0, int tr=q-1){
    if (l > r) return dummy;
    if (r < tl || tr < l) return dummy;
    if (l <= tl && tr <= r) return st[node];
    int tm = (tl+tr)/2;
    vector<ll> res = dummy;
    if (l <= tm) res = query(l, r, node*2, tl, tm);
    if (tm+1 <= r) merge(res, res, query(l, r, node*2+1, tm+1, tr));
    return res;
}

int solve(int c){
    //cout << endl << c << endl;
    int lo=-1, hi=q;
    while (lo < hi-1){
        int mid = (lo+hi)/2;
        vector<ll> res = query(mid, q-1);
        if (res[1]-res[3] >= c) lo = mid;
        else hi = mid;
    }
    //cout << lo << endl;
    if (lo == -1) return st[1][0];
    if (v[lo] > 0){
        //cout << "a" << endl;
        if (lo == q-1) return c;
        int loc = query(lo+1, q-1)[2];
        //cout << loc << endl;
        return c+query(loc+1, q-1)[0];
    }
    else {
        //cout << "b" << endl;
        if (lo == q-1) return 0;
        vector<ll> res = query(lo+1, q-1);
        int loc = query(lo+1, q-1)[4];
        //cout << loc << endl;
        return query(loc+1, q-1)[0];
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    ::v = v;
    int n = c.size();
    q = l.size();
    st.resize(4*q, dummy);
    for (int i=0; i<q; i++) update(i, v[i]);
    vector<int> res(n);
    for (int i=0; i<n; i++) res[i] = solve(c[i]);
    return res;
}

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