oj.uz

Submission #721372

# Submission time Handle Problem Language Result Execution time Memory
721372 2023-04-10T18:56:02 Z urosk Distributing Candies (IOI21_candies) C++17
8 / 100
 776 ms 50112 KB 
#include "candies.h"
#define here cerr<<"======================================\n"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define llinf 10000000000LL
#define dbg(x) cerr<<#x<<": "<<x<<endl

using namespace std;
#define maxn 200005
ll n,q;
ll c[maxn];
vector<pll> v[maxn];
ll lazy[2*maxn];
ll ls[2*maxn],rs[2*maxn],root,tsz = 0;
struct nod{
    ll mx,mn,mxid,mnid,val;
} t[2*maxn];
nod def,def0;
nod f(nod l,nod r){
    nod ans;
    ans.mn = min(l.mn,r.mn);
    ans.mx = max(l.mx,r.mx);
    if(l.mn<r.mn) ans.mnid = l.mnid;
    else ans.mnid = r.mnid;
    if(l.mx>r.mx) ans.mxid = l.mxid;
    else ans.mxid = r.mxid;
    ans.val = ans.mx-ans.mn;
    return ans;
}
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    t[v].mn = 0;
    t[v].mx = 0;
    t[v].mxid = tr;
    t[v].mnid = tr;
    t[v].val = 0;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void push(ll v,ll tl,ll tr){
    if(lazy[v]==0) return;
    t[v].mn+=lazy[v];
    t[v].mx+=lazy[v];
    if(tl<tr){
        lazy[ls[v]]+=lazy[v];
        lazy[rs[v]]+=lazy[v];
    }
    lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
    push(v,tl,tr);
    if(l>r||tl>tr||l>tr||tl>r) return;
    if(tl>=l&&tr<=r){
        lazy[v]+=x;
        push(v,tl,tr);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,x);
    upd(rs[v],mid+1,tr,l,r,x);
    t[v] = f(t[ls[v]],t[rs[v]]);
}
ll get(ll v,ll tl,ll tr,ll x,nod cur){
    push(v,tl,tr);
    nod cur2 = f(t[v],cur);
    if(cur2.val<x) return -1;
    if(tl==tr) return tl;
    ll mid = (tl+tr)/2;
    push(ls[v],tl,tr);
    push(rs[v],mid+1,tr);
    ll ans = get(rs[v],mid+1,tr,x,cur);
    if(ans==-1) return get(ls[v],tl,mid,x,f(t[rs[v]],cur));
    return ans;
}
nod get(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r||l>tr||tl>tr||tl>r) return def0;
    if(tl>=l&&tr<=r) return t[v];
    ll mid = (tl+tr)/2;
    return f(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r));
}
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];
    for(ll i = 1;i<=q;i++){
        v[L[i-1]+1].pb({VAL[i-1],i+2});
        v[R[i-1]+2].pb({-VAL[i-1],i+2});
    }
    q+=2;
    init(root,1,q);
    upd(1,1,q,1,q,llinf);
    upd(1,1,q,2,q,-llinf);
    ll sum = 0;
    nod def0;
    def0.mn = def0.mx = 0;
    def0.mnid = def0.mxid = q+1;
    def0.val = 0;
    for(ll i = 1;i<=n;i++){
        for(pll p : v[i]){
            ll x = p.fi;
            ll i = p.sc;
            upd(root,1,q,i,q,x);
            sum+=x;
        }
        nod def;
        def.mn = llinf;
        def.mx = -llinf;
        def.mxid = q+1;
        def.mnid = q+1;
        def.val = 0;
        ll j = get(1,1,q,c[i],def);
        nod cur = get(1,1,q,j,q);
        ll minid = cur.mnid;
        ll maxid = cur.mxid;
        if(minid>maxid) ans.pb(min(c[i],sum-cur.mn));
        else ans.pb(max(0LL,c[i]+(sum-cur.mx)));
    }
    return ans;
}
/**
3
10 15 13
2
0 2 20
0 1 -11

3
10 15 13
2
0 1 13
1 2 7
**/

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 49944 KB Output is correct
2 Correct 776 ms 50096 KB Output is correct
3 Correct 748 ms 50112 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 422 ms 43644 KB Output isn't correct
3 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 Correct 3 ms 4948 KB Output is correct
3 Incorrect 134 ms 41172 KB Output isn't correct
4 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 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5448 KB Output isn't correct
4 Halted 0 ms 0 KB -