oj.uz

Submission #721122

# Submission time Handle Problem Language Result Execution time Memory
721122 2023-04-10T10:26:27 Z urosk Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 23096 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define dbg(x) cerr<#x<<": "<<x<<endl;

using namespace std;
#define maxn 200005
ll n,q;
ll a[maxn],c[maxn];
vector<pll> t[2*maxn];
ll ls[2*maxn],rs[2*maxn],root = 0,tsz = 0;
void init(ll &v,ll tl,ll tr){
    t[v].clear();
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,ll l,ll r,pll p){
    if(l>r||tl>tr||l>tr||tl>r) return;
    if(tl>=l&&tr<=r){t[v].pb(p);return;}
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,p);
    upd(rs[v],mid+1,tr,l,r,p);
}
set<pll> cur;
void reshi(ll v,ll tl,ll tr){
    for(pll p : t[v]) cur.insert(p);
    ll mid = (tl+tr)/2;
    if(tl==tr){
        ll i = tl;
        for(pll p : cur){
            a[i]+=p.sc;
            if(a[i]<0) a[i] = 0;
            if(a[i]>c[i]) a[i] = c[i];
        }
        goto lol;
    }
    reshi(ls[v],tl,mid);
    reshi(rs[v],mid+1,tr);
    lol:;
    for(pll p : t[v]){
        cur.erase(cur.find(p));
    }
}
ll d = 400;
vector<int> ans;
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> VAL) {
    n = C.size();
    q = L.size();
    for(ll i = 1;i<=n;i++) c[i] = C[i-1];
    sort(a+1,a+1+n);
    init(root,1,n);
    for(ll i = 1;i<=q;i++){
        ll l = L[i-1] + 1;
        ll r = R[i-1] + 1;
        ll val = VAL[i-1];
        if(i%d==0){
            reshi(root,1,n);
            init(root,1,n);
        }
        upd(root,1,n,l,r,{i,val});
    }
    reshi(root,1,n);
    for(ll i = 1;i<=n;i++) ans.pb(a[i]);
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 20 ms 9940 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 1142 ms 14844 KB Output is correct
3 Correct 750 ms 19312 KB Output is correct
4 Execution timed out 5053 ms 22964 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 2512 ms 14500 KB Output is correct
4 Correct 2511 ms 17784 KB Output is correct
5 Execution timed out 5053 ms 20616 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 8 ms 9684 KB Output is correct
5 Correct 20 ms 9940 KB Output is correct
6 Execution timed out 5047 ms 23096 KB Time limit exceeded
7 Halted 0 ms 0 KB -