oj.uz

Submission #535591

# Submission time Handle Problem Language Result Execution time Memory
535591 2022-03-10T15:25:09 Z mario05092929 Distributing Candies (IOI21_candies) C++17
8 / 100
 5000 ms 36632 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,idx-1,idx-1);
            if(bef < mn) ans.pb((ll)a[i]-(mx-querySum(1,0,Q,0,Q)));
            else if(bef > mx) ans.pb(querySum(1,0,Q,0,Q)-mn);
            else while(1);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1320 ms 36608 KB Output is correct
2 Correct 1316 ms 36580 KB Output is correct
3 Correct 1374 ms 36632 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -