Submission #1269009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269009		AlgorithmWarrior	Distributing Candies (IOI21_candies)	C++20	100 / 100	298 ms	36360 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int const MAX=200005;
ll const INF=1e18;

struct node{
    ll mn,mx,lazy;
};

struct segment_tree{
    node v[4*MAX];
    void propagate(int nod){
        if(v[nod].lazy){
            ll lz=v[nod].lazy;
            v[2*nod].mn+=lz;
            v[2*nod].mx+=lz;
            v[2*nod].lazy+=lz;
            v[2*nod+1].mn+=lz;
            v[2*nod+1].mx+=lz;
            v[2*nod+1].lazy+=lz;
            v[nod].lazy=0;
        }
    }
    void combine(int nod){
        v[nod].mn=min(v[2*nod].mn,v[2*nod+1].mn);
        v[nod].mx=max(v[2*nod].mx,v[2*nod+1].mx);
    }
    void update(int nod,int st,int dr,int a,int b,int del){
        if(a<=st && dr<=b){
            v[nod].mn+=del;
            v[nod].mx+=del;
            v[nod].lazy+=del;
        }
        else{
            propagate(nod);
            int mij=(st+dr)/2;
            if(a<=mij)
                update(2*nod,st,mij,a,b,del);
            if(mij<b)
                update(2*nod+1,mij+1,dr,a,b,del);
            combine(nod);
        }
    }
    ll query(int nod,int st,int dr,int poz){
        if(st==dr)
            return v[nod].mn;
        propagate(nod);
        int mij=(st+dr)/2;
        if(poz<=mij)
            return query(2*nod,st,mij,poz);
        else
            return query(2*nod+1,mij+1,dr,poz);
    }
    int bin_search(int nod,int st,int dr,int lim,ll& mn,ll& mx){
        if(st==dr){
            mn=min(mn,v[nod].mn);
            mx=max(mx,v[nod].mx);
            return st;
        }
        propagate(nod);
        int mij=(st+dr)/2;
        if(max(mx,v[2*nod+1].mx)-min(mn,v[2*nod+1].mn)>lim)
            return bin_search(2*nod+1,mij+1,dr,lim,mn,mx);
        else{
            mn=min(mn,v[2*nod+1].mn);
            mx=max(mx,v[2*nod+1].mx);
            return bin_search(2*nod,st,mij,lim,mn,mx);
        }
    }
}aint;

vector<int>adauga[MAX];
vector<int>sterge[MAX];

vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
    int n=c.size();
    int q=v.size();
    int i;
    for(i=0;i<q;++i){
        adauga[l[i]].push_back(i+1);
        sterge[r[i]+1].push_back(i+1);
    }
    vector<int>ans(n);
    for(i=0;i<n;++i){
        for(auto qr : adauga[i])
            aint.update(1,0,q,qr,q,v[qr-1]);
        for(auto qr : sterge[i])
            aint.update(1,0,q,qr,q,-v[qr-1]);
        if(aint.v[1].mx-aint.v[1].mn<=c[i])
            ans[i]=aint.query(1,0,q,q)-aint.v[1].mn;
        else{
            ll mn=INF,mx=-INF;
            int poz=aint.bin_search(1,0,q,c[i],mn,mx);
            if(mn==aint.query(1,0,q,poz))
                ans[i]=aint.query(1,0,q,q)-mx+c[i];
            else
                ans[i]=aint.query(1,0,q,q)-mn;
        }
    }
    return ans;
}

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