oj.uz

Submission #435997

# Submission time Handle Problem Language Result Execution time Memory
435997 2021-06-24T04:39:00 Z 79brue Distributing Candies (IOI21_candies) C++17
59 / 100
 5000 ms 29324 KB 
#include <bits/stdc++.h>
#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;
        vector<pair<ll, int> > vec;
        vec.swap(queries[i]);

        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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 18 ms 5260 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 26544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 1283 ms 13008 KB Output is correct
3 Correct 136 ms 19456 KB Output is correct
4 Correct 3082 ms 27068 KB Output is correct
5 Correct 3245 ms 27116 KB Output is correct
6 Correct 3250 ms 27100 KB Output is correct
7 Correct 3157 ms 27116 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 98 ms 13000 KB Output is correct
4 Correct 128 ms 21156 KB Output is correct
5 Correct 4332 ms 29236 KB Output is correct
6 Correct 4291 ms 29132 KB Output is correct
7 Correct 4017 ms 29324 KB Output is correct
8 Correct 4184 ms 28936 KB Output is correct
9 Correct 2796 ms 29012 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 18 ms 5260 KB Output is correct
6 Execution timed out 5062 ms 26544 KB Time limit exceeded
7 Halted 0 ms 0 KB -