Submission #1156031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156031		ace5	Distributing Candies (IOI21_candies)	C++20	100 / 100	1091 ms	31548 KiB

candies

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

using namespace std;

typedef long long ll;

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

pair<ll,ll> segTree[4*maxn];
ll p[4*maxn];

void push(int l,int r,int indV)
{
    segTree[indV].first += p[indV];
    segTree[indV].second += p[indV];
    if(l != r)
    {
        p[indV*2+1] += p[indV];
        p[indV*2+2] += p[indV];
    }
    p[indV] = 0;
    return ;
}
void modify(int lx,int rx,ll x,int l,int r,int indV)
{
    push(l,r,indV);
    if(l > rx || r < lx)
        return ;
    else if(l >= lx && r <= rx)
    {
        p[indV] += x;
        push(l,r,indV);
        return ;
    }
    int m = (l+r)/2;
    modify(lx,rx,x,l,m,indV*2+1);
    modify(lx,rx,x,m+1,r,indV*2+2);
    segTree[indV] = {min(segTree[indV*2+1].first,segTree[indV*2+2].first),max(segTree[indV*2+1].second,segTree[indV*2+2].second)};
    return ;
}
pair<ll,ll> get(int lx,int rx,int l,int r,int indV)
{
    push(l,r,indV);
    if(l > rx || r < lx)
        return {INF,-INF};
    else if(l >= lx && r <= rx)
        return segTree[indV];
    int m = (l+r)/2;
    pair<ll,ll> sl = get(lx,rx,l,m,indV*2+1);
    pair<ll,ll> sr = get(lx,rx,m+1,r,indV*2+2);
    return {min(sl.first,sr.first),max(sl.second,sr.second)};
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int n = c.size();
    int q = l.size();
    vector<vector<pair<int,int>>> ev(n+1);
    for(int j = 0;j < q;++j)
    {
        ev[l[j]].push_back({v[j],j+1});
        ev[r[j]+1].push_back({-v[j],j+1});
    }
    vector<int> s(n);
    ll sum = 0;
    for(int j = 0;j < n;++j)
    {
        for(int k = 0;k < ev[j].size();++k)
        {
            modify(ev[j][k].second,q,ev[j][k].first,0,q,0);
            sum += ev[j][k].first;
        }
        push(0,q,0);
        if(segTree[0].second - segTree[0].first < c[j])
        {
            s[j] = sum - segTree[0].first;
        }
        else
        {
            int lg = 0,rg = q;
            while(lg < rg)
            {
                int mg = (lg+rg)/2;
                pair<ll,ll> cc = get(mg,q,0,q,0);
                if(cc.second-cc.first >= c[j])
                {
                    lg = mg + 1;
                }
                else
                    rg = mg;
            }
            pair<ll,ll> cx = get(lg,q,0,q,0);
            pair<ll,ll> cxd = get(lg-1,q,0,q,0);
            if(cxd.first == cx.first)
            {
                s[j] = sum - cx.first;
            }
            else
                s[j] = sum - cx.second + c[j];
        }
    }
    return s;
}

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