oj.uz

Submission #535592

# Submission time Handle Problem Language Result Execution time Memory
535592 2022-03-10T15:30:45 Z mario05092929 Distributing Candies (IOI21_candies) C++17
100 / 100
 1381 ms 43356 KB 
#include "candies.h"
#define x first
#define y second
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vec;
typedef pair <int,int> pi;
typedef long long ll;
ll a[200005],ql[200005],qr[200005],qv[200005];
int n,Q;
ll sum[800025],mx[800025],mn[800025];
vec q[200005];

void update(int x,int l,int r,int wi,int val) {
    if(wi < l||r < wi) return;
    if(l == r) {
        sum[x] = mx[x] = mn[x] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(x*2,l,mid,wi,val), update(x*2+1,mid+1,r,wi,val);
    sum[x] = sum[x*2]+sum[x*2+1];
    mx[x] = max(mx[x*2],sum[x*2]+mx[x*2+1]);
    mn[x] = min(mn[x*2],sum[x*2]+mn[x*2+1]);
}

ll querySum(int x,int l,int r,int rl,int rr) {
    if(rl > r||l > rr) return 0;
    if(rl <= l&&r <= rr) return sum[x];
    int mid = (l + r) >> 1;
    return querySum(x*2,l,mid,rl,rr)+querySum(x*2+1,mid+1,r,rl,rr);
}

ll queryMx(int x,int l,int r,int rl,int rr,ll cnt) {
    if(rl > r||l > rr) return -1e18;
    if(rl <= l&&r <= rr) return mx[x]+cnt;
    int mid = (l + r) >> 1;
    return max(queryMx(x*2,l,mid,rl,rr,cnt),queryMx(x*2+1,mid+1,r,rl,rr,cnt+sum[x*2]));
}

ll queryMn(int x,int l,int r,int rl,int rr,ll cnt) {
    if(rl > r||l > rr) return 1e18;
    if(rl <= l&&r <= rr) return mn[x]+cnt;
    int mid = (l + r) >> 1;
    return min(queryMn(x*2,l,mid,rl,rr,cnt),queryMn(x*2+1,mid+1,r,rl,rr,cnt+sum[x*2]));
}

vec distribute_candies(vec C,vec L,vec R,vec V) {
    n = C.size(), Q = L.size();
    for(int i = 0;i < n;i++) {
        a[i+1] = C[i];
    }
    for(int i = 0;i < Q;i++) {
        ql[i+1] = L[i]+1;
        qr[i+1] = R[i]+1;
        qv[i+1] = V[i];
        q[ql[i+1]].pb(i+1);
        q[qr[i+1]+1].pb(-i-1);
    }
    vec ans;
    for(int i = 1;i <= n;i++) {
        for(int j : q[i]) {
            if(j > 0) update(1,0,Q,j,qv[j]);
            else update(1,0,Q,-j,0);
        }
        int l = 0, r = Q;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(queryMx(1,0,Q,mid,Q,0)-queryMn(1,0,Q,mid,Q,0) > a[i]) l = mid+1;
            else r = mid;
        }
        int idx = l;
        if(!idx) ans.pb(querySum(1,0,Q,0,Q)-queryMn(1,0,Q,0,Q,0));
        else {
            ll mn = queryMn(1,0,Q,idx,Q,0);
            ll mx = queryMx(1,0,Q,idx,Q,0);
            ll bef = querySum(1,0,Q,0,idx-1);
            if(bef < mn) ans.pb((ll)a[i]-(mx-querySum(1,0,Q,0,Q)));
            else ans.pb(querySum(1,0,Q,0,Q)-mn);
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 7 ms 5332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1221 ms 36596 KB Output is correct
2 Correct 1317 ms 36564 KB Output is correct
3 Correct 1381 ms 36580 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 230 ms 29044 KB Output is correct
3 Correct 363 ms 10528 KB Output is correct
4 Correct 1299 ms 36692 KB Output is correct
5 Correct 1302 ms 42848 KB Output is correct
6 Correct 1135 ms 43356 KB Output is correct
7 Correct 1110 ms 42740 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 106 ms 28420 KB Output is correct
4 Correct 361 ms 9500 KB Output is correct
5 Correct 972 ms 32896 KB Output is correct
6 Correct 967 ms 37060 KB Output is correct
7 Correct 931 ms 37720 KB Output is correct
8 Correct 986 ms 36368 KB Output is correct
9 Correct 1133 ms 37872 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 7 ms 5332 KB Output is correct
6 Correct 1221 ms 36596 KB Output is correct
7 Correct 1317 ms 36564 KB Output is correct
8 Correct 1381 ms 36580 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 230 ms 29044 KB Output is correct
11 Correct 363 ms 10528 KB Output is correct
12 Correct 1299 ms 36692 KB Output is correct
13 Correct 1302 ms 42848 KB Output is correct
14 Correct 1135 ms 43356 KB Output is correct
15 Correct 1110 ms 42740 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 106 ms 28420 KB Output is correct
19 Correct 361 ms 9500 KB Output is correct
20 Correct 972 ms 32896 KB Output is correct
21 Correct 967 ms 37060 KB Output is correct
22 Correct 931 ms 37720 KB Output is correct
23 Correct 986 ms 36368 KB Output is correct
24 Correct 1133 ms 37872 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 365 ms 10828 KB Output is correct
27 Correct 237 ms 31552 KB Output is correct
28 Correct 1251 ms 41276 KB Output is correct
29 Correct 1264 ms 41500 KB Output is correct
30 Correct 1198 ms 41716 KB Output is correct
31 Correct 1228 ms 41940 KB Output is correct
32 Correct 1215 ms 42200 KB Output is correct