Submission #1290336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290336		MMihalev	Distributing Candies (IOI21_candies)	C++20	0 / 100	5093 ms	30052 KiB

candies

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include "candies.h"
using namespace std;
const int MAX_N=2e5+5;
const int BUFF=500;
vector<int>cap;
vector<long long>a,nxt;
vector<pair<int,long long>>queries;
set<pair<int,long long>>curqueries;
void solve(int l,int r)
{
    queries.clear();
    for(auto x:curqueries)queries.push_back(x);

    vector<long long>p,nxt;
    p.resize((int)queries.size());
    nxt.resize((int)queries.size());

    p[0]=queries[0].second;
    for(int i=1;i<queries.size();i++)
    {
        p[i]=p[i-1]+queries[i].second;
    }

    nxt[queries.size()-1]=queries.size()-1;
    for(int i=queries.size()-2;i>=0;i--)
    {
        nxt[i]=queries.size()-1;
        for(int j=i+1;j<queries.size();j++)
        {
            if(p[j]<p[i]){nxt[i]=j;break;}
        }
    }

    vector<pair<long long,int>>nums;
    for(int i=l;i<=r;i++)
    {
        nums.push_back({a[i],i});
    }
    sort(nums.begin(),nums.end());

    int id=0;
    for(auto [num,i]:nums)
    {
        while(p[id]+a[i]>0 && id<p.size())id++;

        if(id==p.size())
        {
            a[i]-=p.back();
        }
        else
        {
            a[i]=min((long long)cap[i],p.back()-p[id]);
        }
    }
}
vector<pair<pair<int,int>,pair<int,int>>>buffer;
vector<pair<int,int>>beg[MAX_N],en[MAX_N];
int N;
void clearbuffer()
{
    for(int i=0;i<=N;i++)
    {
        beg[i].clear();en[i].clear();
    }
    for(auto [f,s]:buffer)
    {
        int l,r,i,val;
        l=f.first;r=f.second;i=s.first;val=s.second;

        beg[l].push_back({i,val});
        en[r+1].push_back({i,val});
    }

    curqueries.clear();
    int prevpoint=-1;
    for(int i=0;i<=N;i++)
    {
        if(en[i].size() && prevpoint!=-1)
        {
            solve(prevpoint,i-1);
        }
        for(auto x:en[i])
        {
            curqueries.erase(x);
        }
        if(en[i].size() && curqueries.size())prevpoint=i-1;
        if(curqueries.size()==0)prevpoint=-1;

        if(beg[i].size() && prevpoint!=-1)
        {
            solve(prevpoint,i-1);
        }
        for(auto x:beg[i])
        {
            curqueries.insert(x);
        }
        if(beg[i].size())prevpoint=i;
    }
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v)
{
    cap=c;
    N=cap.size();
    a.resize((int)cap.size());


    for(int i=0;i<l.size();i++)
    {
        buffer.push_back({{l[i],r[i]},{i,v[i]}});
        if(buffer.size()==BUFF)
        {
            clearbuffer();
        }
    }
    if(buffer.size())
    {
        clearbuffer();
    }

    vector<int>aa;
    for(int x:a)
    {
        aa.push_back(x);
    }
    return aa;
}

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