oj.uz

Submission #721393

# Submission time Handle Problem Language Result Execution time Memory
721393 2023-04-10T19:38:20 Z urosk Distributing Candies (IOI21_candies) C++17
8 / 100
 874 ms 50060 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 10000000000000000LL
#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){
    if(l.mn>r.mn) swap(l,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);
    ll sum = 0;
    nod def0;
    def0.mn = llinf;
    def0.mx = -llinf;
    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;
        }
        push(1,1,q);
        if(t[1].val<=c[i]){
            if(t[1].mx>c[i]) ans.pb(c[i]+(sum-t[1].mx));
            else{
                ll j = t[1].mnid;
                if(t[1].mn<0) ans.pb(sum-t[1].mn);
                else ans.pb(sum);
            }
            continue;
        }
        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)));
    }
    for(ll i = 0;i<n;i++) ans[i] = max(0LL,min(c[i+1],(ll)ans[i]));
    return ans;
}
/**
3
10 15 13
2
0 2 20
0 1 -11

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

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:117:20: warning: unused variable 'j' [-Wunused-variable]
  117 |                 ll j = t[1].mnid;
      |                    ^

Subtask #1
0 / 3.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 4 ms 5332 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 874 ms 50060 KB Output is correct
2 Correct 853 ms 49980 KB Output is correct
3 Correct 836 ms 49960 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 515 ms 43772 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 171 ms 41192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.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 4 ms 5332 KB Output isn't correct
4 Halted 0 ms 0 KB -