oj.uz

Submission #548535

# Submission time Handle Problem Language Result Execution time Memory
548535 2022-04-13T18:10:25 Z FEDIKUS Distributing Candies (IOI21_candies) C++17
100 / 100
 465 ms 35692 KB 
#include "candies.h"

#include<iostream>
#include <vector>

using namespace std;

typedef long long ll;

const ll maxn=2e5+10;
const ll inf=1e9+10;

struct node{
    ll min,max,lazy;
};

ll n,q,val=0;
vector<pair<ll,ll> > events[maxn];
vector<int> vv;
node segt[4*maxn];

void ispisi(node a){
    //cout<<a.min<<" "<<a.max<<" "<<a.lazy<<"\n";
}

node comb(node a,node b){
    node ret;
    ret.lazy=0;
    ret.max=max(a.max,b.max);
    ret.min=min(a.min,b.min);
    return ret;
}

void push(ll ind,ll l,ll r){
    if(segt[ind].lazy==0) return;
    if(l!=r){
        segt[2*ind].min+=segt[ind].lazy; segt[2*ind].max+=segt[ind].lazy;
        segt[2*ind+1].min+=segt[ind].lazy; segt[2*ind+1].max+=segt[ind].lazy;
        segt[2*ind].lazy+=segt[ind].lazy;
        segt[2*ind+1].lazy+=segt[ind].lazy;
    }
    segt[ind].lazy=0;
}

void update(ll tl,ll tr,ll v,ll ind=1,ll l=0,ll r=q-1){
    push(ind,l,r);
    if(tl<=l && r<=tr){
        segt[ind].lazy+=v;
        segt[ind].min+=v;
        segt[ind].max+=v;
        return;
    }
    ll mid=l+(r-l)/2;
    if(tl<=mid) update(tl,tr,v,2*ind,l,mid);
    if(tr>mid) update(tl,tr,v,2*ind+1,mid+1,r);
    segt[ind]=comb(segt[2*ind],segt[2*ind+1]);
}

node qr(ll tl,ll tr,ll ind=1,ll l=0,ll r=q-1){
    push(ind,l,r);
    if(tl<=l && r<=tr){
        return segt[ind];
    }
    ll mid=l+(r-l)/2;
    node ret={inf*inf,-inf*inf,0};
    if(tl<=mid) ret=comb(ret,qr(tl,tr,2*ind,l,mid));
    if(tr>mid) ret=comb(ret,qr(tl,tr,2*ind+1,mid+1,r));
    return ret;
}

ll query(ll c){
    ll ind=1,l=0,r=q-1,res=-1;
    ll tmax=-inf*inf,tmin=inf*inf;
    while(true){ //trazim prvi na kome je razlika <=c
        push(ind,l,r);
        if(l==r){
            if(max(tmax,segt[ind].max)-min(tmin,segt[ind].min)<=c){
                res=l;
                tmax=max(tmax,segt[ind].max);
                tmin=min(tmin,segt[ind].min);
            }
            break;
        }
        if(max(tmax,segt[2*ind+1].max)-min(tmin,segt[2*ind+1].min)<=c){
            res=l+(r-l)/2+1;
            r=l+(r-l)/2;
            tmax=max(tmax,segt[2*ind+1].max);
            tmin=min(tmin,segt[2*ind+1].min);
            ind=2*ind;
        }else{
            ind=2*ind+1;
            l=l+(r-l)/2+1;
        }
    }
    if(vv[res]>0){
        return val-(tmax-c);
    }else{
        return val-tmin;
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n=c.size();
    q=l.size()+1;
    l.insert(l.begin(),0);
    r.insert(r.begin(),n-1);
    v.insert(v.begin(),-inf);
    vv=v;
    for(ll i=0;i<q;i++){
        events[l[i]].push_back({i,v[i]});
        events[r[i]+1].push_back({i,-v[i]});
    }
    vector<int> ans(n);
    for(ll i=0;i<n;i++){
        for(auto event:events[i]){
            val+=event.second;
            update(event.first,q-1,event.second);
        }
        ans[i]=query(c[i]);
    }
    return ans;
}

Subtask #1
3.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 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5300 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 35668 KB Output is correct
2 Correct 389 ms 35620 KB Output is correct
3 Correct 398 ms 35608 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 265 ms 31700 KB Output is correct
3 Correct 59 ms 8764 KB Output is correct
4 Correct 416 ms 35624 KB Output is correct
5 Correct 372 ms 35560 KB Output is correct
6 Correct 465 ms 35624 KB Output is correct
7 Correct 406 ms 35616 KB Output is correct

Subtask #4
29.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 Correct 113 ms 30452 KB Output is correct
4 Correct 57 ms 7612 KB Output is correct
5 Correct 185 ms 32004 KB Output is correct
6 Correct 188 ms 31960 KB Output is correct
7 Correct 216 ms 32000 KB Output is correct
8 Correct 173 ms 32144 KB Output is correct
9 Correct 189 ms 31996 KB Output is correct

Subtask #5
33.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 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5300 KB Output is correct
6 Correct 417 ms 35668 KB Output is correct
7 Correct 389 ms 35620 KB Output is correct
8 Correct 398 ms 35608 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 265 ms 31700 KB Output is correct
11 Correct 59 ms 8764 KB Output is correct
12 Correct 416 ms 35624 KB Output is correct
13 Correct 372 ms 35560 KB Output is correct
14 Correct 465 ms 35624 KB Output is correct
15 Correct 406 ms 35616 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 113 ms 30452 KB Output is correct
19 Correct 57 ms 7612 KB Output is correct
20 Correct 185 ms 32004 KB Output is correct
21 Correct 188 ms 31960 KB Output is correct
22 Correct 216 ms 32000 KB Output is correct
23 Correct 173 ms 32144 KB Output is correct
24 Correct 189 ms 31996 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 61 ms 7576 KB Output is correct
27 Correct 239 ms 31764 KB Output is correct
28 Correct 393 ms 35692 KB Output is correct
29 Correct 437 ms 35616 KB Output is correct
30 Correct 393 ms 35596 KB Output is correct
31 Correct 393 ms 35604 KB Output is correct
32 Correct 411 ms 35604 KB Output is correct