oj.uz

Submission #548533

# Submission time Handle Problem Language Result Execution time Memory
548533 2022-04-13T18:08:02 Z FEDIKUS Distributing Candies (IOI21_candies) C++17
100 / 100
 1799 ms 42512 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,tmin=inf;
    /*while(true){ //trazim prvi na kome je razlika <=c
        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;
        }
    }*/
    while(l<=r){
        int mid=l+(r-l)/2;
        //cout<<"ovo "<<l<<" "<<r<<" "<<qr(mid,q-1).max<<" "<<qr(mid,q-1).min<<"\n";
        if(qr(mid,q-1).max-qr(mid,q-1).min<=c){
            res=mid;
            r=mid-1;
        }else l=mid+1;
    }
    tmax=qr(res,q-1).max;
    tmin=qr(res,q-1).min;
    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;
}

Compilation message

candies.cpp: In function 'll query(ll)':
candies.cpp:72:8: warning: unused variable 'ind' [-Wunused-variable]
   72 |     ll ind=1,l=0,r=q-1,res=-1;
      |        ^~~

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1681 ms 38464 KB Output is correct
2 Correct 1731 ms 39680 KB Output is correct
3 Correct 1741 ms 39452 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 308 ms 33428 KB Output is correct
3 Correct 566 ms 10972 KB Output is correct
4 Correct 1799 ms 41564 KB Output is correct
5 Correct 1734 ms 42072 KB Output is correct
6 Correct 1654 ms 42512 KB Output is correct
7 Correct 1694 ms 41744 KB Output is correct

Subtask #4
29.0 / 29.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 140 ms 31824 KB Output is correct
4 Correct 508 ms 8748 KB Output is correct
5 Correct 1386 ms 33048 KB Output is correct
6 Correct 1380 ms 33048 KB Output is correct
7 Correct 1333 ms 33048 KB Output is correct
8 Correct 1453 ms 35436 KB Output is correct
9 Correct 1614 ms 36916 KB Output is correct

Subtask #5
33.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 Correct 4 ms 5300 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 11 ms 5332 KB Output is correct
6 Correct 1681 ms 38464 KB Output is correct
7 Correct 1731 ms 39680 KB Output is correct
8 Correct 1741 ms 39452 KB Output is correct
9 Correct 3 ms 4952 KB Output is correct
10 Correct 308 ms 33428 KB Output is correct
11 Correct 566 ms 10972 KB Output is correct
12 Correct 1799 ms 41564 KB Output is correct
13 Correct 1734 ms 42072 KB Output is correct
14 Correct 1654 ms 42512 KB Output is correct
15 Correct 1694 ms 41744 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 140 ms 31824 KB Output is correct
19 Correct 508 ms 8748 KB Output is correct
20 Correct 1386 ms 33048 KB Output is correct
21 Correct 1380 ms 33048 KB Output is correct
22 Correct 1333 ms 33048 KB Output is correct
23 Correct 1453 ms 35436 KB Output is correct
24 Correct 1614 ms 36916 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 517 ms 8856 KB Output is correct
27 Correct 256 ms 34284 KB Output is correct
28 Correct 1650 ms 40192 KB Output is correct
29 Correct 1657 ms 40672 KB Output is correct
30 Correct 1729 ms 40744 KB Output is correct
31 Correct 1691 ms 40948 KB Output is correct
32 Correct 1619 ms 41188 KB Output is correct