oj.uz

답안 #548519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548519 2022-04-13T17:32:24 Z FEDIKUS 사탕 분배 (IOI21_candies) C++17
0 / 100
 1645 ms 36404 KB 
#include "candies.h"

#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,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;
        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()+2;
    l.insert(l.begin(),0); l.insert(l.begin(),0);
    r.insert(r.begin(),n-1); r.insert(r.begin(),n-1);
    v.insert(v.begin(),-inf); 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:71:8: warning: unused variable 'ind' [-Wunused-variable]
   71 |     ll ind=1,l=0,r=q-1,res=-1;
      |        ^~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1645 ms 36404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 224 ms 32164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 131 ms 30880 KB Output is correct
4 Correct 533 ms 7968 KB Output is correct
5 Correct 1529 ms 32252 KB Output is correct
6 Correct 1420 ms 32272 KB Output is correct
7 Incorrect 1323 ms 32192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -