oj.uz

Submission #435999

# Submission time Handle Problem Language Result Execution time Memory
435999 2021-06-24T04:40:14 Z 79brue Distributing Candies (IOI21_candies) C++17
100 / 100
 4703 ms 52788 KB 
#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.0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4670 ms 52148 KB Output is correct
2 Correct 4703 ms 52404 KB Output is correct
3 Correct 4687 ms 52492 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 1154 ms 13316 KB Output is correct
3 Correct 112 ms 25216 KB Output is correct
4 Correct 2791 ms 51672 KB Output is correct
5 Correct 2753 ms 52640 KB Output is correct
6 Correct 2743 ms 52036 KB Output is correct
7 Correct 2723 ms 52788 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 82 ms 13000 KB Output is correct
4 Correct 112 ms 17896 KB Output is correct
5 Correct 2493 ms 25552 KB Output is correct
6 Correct 2437 ms 25644 KB Output is correct
7 Correct 2323 ms 25548 KB Output is correct
8 Correct 2495 ms 25548 KB Output is correct
9 Correct 1210 ms 25644 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 17 ms 5292 KB Output is correct
6 Correct 4670 ms 52148 KB Output is correct
7 Correct 4703 ms 52404 KB Output is correct
8 Correct 4687 ms 52492 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 1154 ms 13316 KB Output is correct
11 Correct 112 ms 25216 KB Output is correct
12 Correct 2791 ms 51672 KB Output is correct
13 Correct 2753 ms 52640 KB Output is correct
14 Correct 2743 ms 52036 KB Output is correct
15 Correct 2723 ms 52788 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 82 ms 13000 KB Output is correct
19 Correct 112 ms 17896 KB Output is correct
20 Correct 2493 ms 25552 KB Output is correct
21 Correct 2437 ms 25644 KB Output is correct
22 Correct 2323 ms 25548 KB Output is correct
23 Correct 2495 ms 25548 KB Output is correct
24 Correct 1210 ms 25644 KB Output is correct
25 Correct 4 ms 4940 KB Output is correct
26 Correct 136 ms 24076 KB Output is correct
27 Correct 1218 ms 13232 KB Output is correct
28 Correct 4515 ms 52184 KB Output is correct
29 Correct 4447 ms 52348 KB Output is correct
30 Correct 4357 ms 51992 KB Output is correct
31 Correct 4254 ms 51972 KB Output is correct
32 Correct 4202 ms 51920 KB Output is correct