Submission #435071

#	Time	Username	Problem	Language	Result	Execution time	Memory
435071		Bench0310	Distributing Candies (IOI21_candies)	C++17	0 / 100	1791 ms	59004 KiB

candies

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

using namespace std;
typedef long long ll;

const ll inf=(1ll<<60);

struct Tag
{
    ll mx;
    ll add;
    Tag(){mx=-inf;add=0;}
    Tag(int a){mx=-inf;add=a;}
    Tag(int a,int b){mx=a;add=b;}
    void apply(Tag t)
    {
        mx+=t.add;
        add+=t.add;
        mx=max(mx,t.mx);
    }
    void reset(){mx=-inf;add=0;}
};

ll mn_d=0;
ll second_mn_d=0;

struct obj
{
    ll mn,second_mn;
    Tag t;
    obj(){mn=0;second_mn=inf;}
    void apply(Tag u)
    {
        mn+=u.add;
        mn_d+=u.add;
        second_mn+=u.add;
        second_mn_d+=u.add;
        if(u.mx>mn)
        {
            mn_d+=(u.mx-mn);
            mn=u.mx;
        }
        t.apply(u);
    }
    void pull(obj a,obj b)
    {
        mn=min(a.mn,b.mn);
        second_mn=inf;
        for(ll x:{a.mn,b.mn,a.second_mn,b.second_mn}) if(x>mn) second_mn=min(second_mn,x);
    }
};

const int N=200005;
vector<int> c(N);
vector<obj> one(4*N);
vector<obj> two(4*N);

void apply_one(int idx,Tag t)
{
    one[idx].apply(t);
    two[idx].mn-=mn_d;
    two[idx].second_mn-=second_mn_d;
    mn_d=0;
    second_mn_d=0;
}

void apply_two(int idx,Tag t)
{
    two[idx].apply(t);
    one[idx].mn-=mn_d;
    one[idx].second_mn-=second_mn_d;
    mn_d=0;
    second_mn_d=0;
}

void push(int idx)
{
    for(int i=0;i<2;i++) apply_one(2*idx+i,one[idx].t);
    one[idx].t.reset();
    for(int i=0;i<2;i++) apply_two(2*idx+i,two[idx].t);
    two[idx].t.reset();
}

void pull(int idx)
{
    one[idx].pull(one[2*idx],one[2*idx+1]);
    two[idx].pull(two[2*idx],two[2*idx+1]);
}

void build(int idx,int l,int r)
{
    if(l==r) two[idx].mn=c[l];
    else
    {
        int m=(l+r)/2;
        build(2*idx,l,m);
        build(2*idx+1,m+1,r);
        pull(idx);
    }
}

void update_add(int idx,int l,int r,int ql,int qr,int x)
{
    if(ql>qr) return;
    if(l==ql&&r==qr) apply_one(idx,Tag(x));
    else
    {
        int m=(l+r)/2;
        push(idx);
        update_add(2*idx,l,m,ql,min(qr,m),x);
        update_add(2*idx+1,m+1,r,max(ql,m+1),qr,x);
        pull(idx);
    }
}

void update_one(int idx,int l,int r)
{
    if(one[idx].mn>=0) return;
    if(one[idx].second_mn>0) apply_one(idx,Tag(0,0));
    else
    {
        int m=(l+r)/2;
        push(idx);
        update_one(2*idx,l,m);
        update_one(2*idx+1,m+1,r);
        pull(idx);
    }
}

void update_two(int idx,int l,int r)
{
    if(two[idx].mn>=0) return;
    if(two[idx].second_mn>0) apply_two(idx,Tag(0,0));
    else
    {
        int m=(l+r)/2;
        push(idx);
        update_two(2*idx,l,m);
        update_two(2*idx+1,m+1,r);
        pull(idx);
    }
}

vector<int> res(N);

void extract(int idx,int l,int r)
{
    if(l==r) res[l]=one[idx].mn;
    else
    {
        int m=(l+r)/2;
        push(idx);
        extract(2*idx,l,m);
        extract(2*idx+1,m+1,r);
    }
}

vector<int> distribute_candies(vector<int> nc,vector<int> nl,vector<int> nr,vector<int> nv)
{
    c=nc;
    int n=nc.size();
    build(1,0,n-1);
    int q=nl.size();
    for(int o=0;o<q;o++)
    {
        int l=nl[o];
        int r=nr[o];
        int x=nv[o];
        update_add(1,0,n-1,l,r,x);
        update_one(1,0,n-1);
        update_two(1,0,n-1);
//        extract(1,0,n-1);
//        cout << "after: ";
//        for(int i=0;i<n;i++) cout << res[i] << " \n"[i==n-1];
    }
    extract(1,0,n-1);
    return res;
}

//int main()
//{
//    
//    return 0;
//}

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