Submission #435999

#	Time	Username	Problem	Language	Result	Execution time	Memory
435999		79brue	Distributing Candies (IOI21_candies)	C++17	100 / 100	4703 ms	52788 KiB

candies

#include <bits/stdc++.h>
#define vec queries[i]
#include "candies.h"

using namespace std;

typedef long long ll;
const int LIM = 500;
const ll INF = 1e18;

int n, q;
ll cap[200002], arr[200002];
int ql[200002], qr[200002];
ll qv[200002];

pair<ll, int> sortedList[200002];
int group[200002];
bool done[200002];
vector<pair<ll, int> > queries[200002];

ll minSum, maxSum, sum, prv;

void solveQuery(int qs, int qe){
    vector<int> ranges {0, n};
    for(int i=qs; i<=qe; i++){
        ranges.push_back(ql[i]);
        ranges.push_back(qr[i]+1);
    }
    sort(ranges.begin(), ranges.end());
    ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());

    int rangeCnt = (int)ranges.size() - 1;
    for(int i=0; i<rangeCnt; i++){
        int l = ranges[i], r = ranges[i+1]-1;
        queries[i].clear();
        for(int j=l; j<=r; j++){
            group[j] = i;
            done[j] = 0;
        }
    }

    for(int i=0; i<n; i++) queries[group[sortedList[i].second]].push_back(sortedList[i]);

    for(int i=0; i<rangeCnt; i++){
        int l = ranges[i], r = ranges[i+1]-1;
        ll A=0, B=INF, C=0;
        for(int j=qs; j<=qe; j++){
            if(r<ql[j] || qr[j]<l) continue;
            C += qv[j];
            A = max(A, -C);
            B = min(B, INF-C);
        }

        for(int j=l; j<=r; j++){
            if(A + (INF-B) > cap[j]) continue;
            done[j] = 1;
            if(arr[j] <= A) arr[j] = A+C;
            else if(cap[j] - arr[j] <= INF - B) arr[j] = B+C + (cap[j] - INF);
            else arr[j] += C;
        }

        minSum = 0;
        maxSum = sum = prv = 0;
        int pnt = 0;
        ll lim = 0;

        for(int j=qe; j>=qs; j--){
            if(r<ql[j] || qr[j]<l) continue;
            sum += qv[j];
            minSum = min(minSum, sum);
            maxSum = max(maxSum, sum);

            ll tmpMax = sum - minSum;
            ll tmpMin = sum - maxSum;
            if(prv >= max(tmpMax, -tmpMin)) continue;
            if(prv < tmpMax){
                while(pnt < (int)vec.size() && vec[pnt].first <= tmpMax){
                    if(!done[vec[pnt].second]) arr[vec[pnt].second] = lim + (vec[pnt].first - prv);
                    pnt++;
                }
                lim += (tmpMax - prv);
            }
            else{
                while(pnt < (int)vec.size() && vec[pnt].first <= -tmpMin){
                    if(!done[vec[pnt].second]) arr[vec[pnt].second] = lim;
                    pnt++;
                }
            }
            prv = max(tmpMax, -tmpMin);
        }
        while(pnt < (int)vec.size()){
            if(!done[vec[pnt].second]) arr[vec[pnt].second] = lim;
            pnt++;
        }
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = (int)c.size();
    for(int i=0; i<n; i++) cap[i] = c[i];
    q = (int)l.size();
    for(int i=0; i<q; i++){
        ql[i] = l[i], qr[i] = r[i], qv[i] = v[i];
    }

    for(int i=0; i<n; i++) sortedList[i] = make_pair(cap[i], i);
    sort(sortedList, sortedList+n);

    for(int i=0; i*LIM<q; i++){
        solveQuery(i*LIM, min(i*LIM+LIM-1, q-1));
    }

    return vector<int> (arr, arr+n);
}

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