Submission #1182916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182916		sleepntsheep	Distributing Candies (IOI21_candies)	C++20	0 / 100	109 ms	34164 KiB

candies

#include "candies.h"
#include<stdio.h>
#include<assert.h>

#include <vector>

struct node{
    long long sum,smx,smn;
    friend node operator+(node a,node b){
        node c;
        c.smx=std::max(a.smx,b.smx);
        c.smn=std::min(a.smn,b.smn);
        c.sum=c.smx-c.smn;
        return c;
    }
    node():sum(0),smx(0),smn(0){ }
    node(long long x):sum(x),smx(x),smn(x){}
};

node t[1<<19];
long long lz[1<<19];
void pus(int v,int l,int r){
    if(lz[v]){
        t[v].smn+=lz[v];
        t[v].smx+=lz[v];
        t[v].sum+=lz[v];
        if(l-r){
            lz[v*2+1]+=lz[v];
            lz[v*2+2]+=lz[v];
        }
        lz[v]=0;
    }
}
void pul(int v,int l,int r){
    if(l!=r) pus(v*2+1,l,(l+r)/2), pus(v*2+2,(l+r)/2+1,r);
    t[v]=t[v*2+1]+t[v*2+2];
}
void update(int v,int l,int r,int x,int y,int k){
    pus(v,l,r);
    if(r<x||y<l)return;
    if(x<=l&&r<=y){
        lz[v]=k;
        pus(v,l,r);return;
    }
    update(v*2+1,l,(l+r)/2,x,y,k);
    update(v*2+2,(l+r)/2+1,r,x,y,k);
    pul(v,l,r);
}
node query(int v,int l,int r,int x,int y){
    pus(v,l,r);
    if(x<=l&&r<=y)return t[v];
    if((l+r)/2<x)return query(v*2+2,(l+r)/2+1,r,x,y);
    if(y<=(l+r)/2)return query(v*2+1,l,(l+r)/2,x,y);
    return query(v*2+1,l,(l+r)/2,x,y)+query(v*2+2,(l+r)/2+1,r,x,y);
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    int n=(int)c.size();

    std::vector<std::vector<int>>attach(n);
    auto ADDQUERY=[&](int l,int r,int v,int id){
        attach[l].push_back(id);
        if(r+1<n)attach[r+1].push_back(id|(1<<25));
    };

    l.insert(l.begin(),0);
    r.insert(r.begin(),n-1);
    l.insert(l.begin(),0);
    r.insert(r.begin(),n-1);
    v.insert(v.begin(),1e9+1);
    v.insert(v.begin(),-1e9-1);
    for(int i=0;i<(int)l.size();++i)
        ADDQUERY(l[i],r[i],v[i],i);

    std::vector<int> s(n);

    int q=(int)l.size();
    for(int i=0;i<n;++i){
        for(auto x:attach[i]){
            if((x>>25)&1){
                x^=1<<25;
                update(0,0,q-1,x,q-1,-v[x]);
            }else{
                update(0,0,q-1,x,q-1,v[x]);
            }
        }

        int lower,upper,mid,i1,i2;

        i1=i2=-1;
        lower=-1,upper=q;
        while(upper-lower>1){
            mid=lower+(upper-lower)/2;
            node x=query(0,0,q-1,mid,q-1);
            if(x.sum>=c[i]) i1=lower=mid;
            else upper=mid;
        }

        assert(~i1);
        lower=i1,upper=q;
        while(upper-lower>1){
            mid=lower+(upper-lower)/2;
            node x=query(0,0,q-1,i1,mid);
            if(x.sum>=c[i]) i2=upper=mid;
            else lower=mid;
        }

        assert(~i2);

        if(query(0,0,q-1,i1,i1).sum<query(0,0,q-1,i2,i2).sum){
            s[i]=c[i]+(query(0,0,q-1,q-1,q-1).sum-query(0,0,q-1,i2,i2).sum);
        }else{
            s[i]=query(0,0,q-1,q-1,q-1).sum-query(0,0,q-1,i2,i2).sum;
        }
    }

    return s;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33