oj.uz

Submission #1060070

# Submission time Handle Problem Language Result Execution time Memory
1060070 2024-08-15T10:27:13 Z thangdz2k7 Distributing Candies (IOI21_candies) C++17
100 / 100
 210 ms 41424 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, q;
vector <int> event[N];
long long sum[4 * N], Max[4 * N], Min[4 * N];

void upd(int u, int val, int s = 1, int l = 0, int r = q - 1){
    if (l == r){
        sum[s] = val;
        Max[s] = max(0, val);
        Min[s] = min(0, val);
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) upd(u, val, 2 * s, l, mid);
    else upd(u, val, 2 * s + 1, mid + 1, r);

    sum[s] = sum[2 * s] + sum[2 * s + 1];
    Max[s] = max(Max[2 * s], sum[2 * s] + Max[2 * s + 1]);
    Min[s] = min(Min[2 * s], sum[2 * s] + Min[2 * s + 1]);
}

long long get(int time, int s = 1, int l = 0, int r = q - 1){
    if (l == r){
        if (sum[s] < 0) return 0;
        if (sum[s] > time) return time;
        return sum[s];
    }

    int mid = l + r >> 1;
    if (Max[2 * s + 1] - Min[2 * s + 1] > time) return get(time, 2 * s + 1, mid + 1, r);
    long long rt = get(time, 2 * s, l, mid);
    if (rt + Max[2 * s + 1] > time) return time - (Max[2 * s + 1] - sum[2 * s + 1]);
    if (rt + Min[2 * s + 1] < 0) return sum[2 * s + 1] - Min[2 * s + 1];
    return rt + sum[2 * s + 1];
}

vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v){
    n = c.size(), q = l.size();
    for (int i = 0; i < q; ++ i){
        event[l[i]].push_back(i + 1);
        event[r[i] + 1].push_back(-i - 1);
    }

    vector <int> ans;
    for (int i = 0; i < n; ++ i){
        for (int id : event[i]){
            if (id < 0) upd(-id - 1, 0);
            else upd(id - 1, v[id - 1]);
        }
        ans.push_back(get(c[i]));
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void upd(int, int, int, int, int)':
candies.cpp:19:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'long long int get(int, int, int, int)':
candies.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9304 KB Output is correct
2 Correct 1 ms 9308 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 35020 KB Output is correct
2 Correct 210 ms 38852 KB Output is correct
3 Correct 188 ms 38600 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 112 ms 31852 KB Output is correct
3 Correct 42 ms 11188 KB Output is correct
4 Correct 173 ms 40700 KB Output is correct
5 Correct 184 ms 41160 KB Output is correct
6 Correct 207 ms 41424 KB Output is correct
7 Correct 177 ms 40904 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 59 ms 28220 KB Output is correct
4 Correct 35 ms 11988 KB Output is correct
5 Correct 95 ms 31168 KB Output is correct
6 Correct 98 ms 31168 KB Output is correct
7 Correct 95 ms 31168 KB Output is correct
8 Correct 99 ms 31168 KB Output is correct
9 Correct 118 ms 31168 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9304 KB Output is correct
2 Correct 1 ms 9308 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 177 ms 35020 KB Output is correct
7 Correct 210 ms 38852 KB Output is correct
8 Correct 188 ms 38600 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 112 ms 31852 KB Output is correct
11 Correct 42 ms 11188 KB Output is correct
12 Correct 173 ms 40700 KB Output is correct
13 Correct 184 ms 41160 KB Output is correct
14 Correct 207 ms 41424 KB Output is correct
15 Correct 177 ms 40904 KB Output is correct
16 Correct 2 ms 9304 KB Output is correct
17 Correct 2 ms 9308 KB Output is correct
18 Correct 59 ms 28220 KB Output is correct
19 Correct 35 ms 11988 KB Output is correct
20 Correct 95 ms 31168 KB Output is correct
21 Correct 98 ms 31168 KB Output is correct
22 Correct 95 ms 31168 KB Output is correct
23 Correct 99 ms 31168 KB Output is correct
24 Correct 118 ms 31168 KB Output is correct
25 Correct 2 ms 9308 KB Output is correct
26 Correct 38 ms 9480 KB Output is correct
27 Correct 100 ms 31316 KB Output is correct
28 Correct 175 ms 39376 KB Output is correct
29 Correct 178 ms 39580 KB Output is correct
30 Correct 170 ms 39884 KB Output is correct
31 Correct 195 ms 40136 KB Output is correct
32 Correct 170 ms 40392 KB Output is correct