oj.uz

Submission #839106

# Submission time Handle Problem Language Result Execution time Memory
839106 2023-08-28T16:15:31 Z andrei_boaca Distributing Candies (IOI21_candies) C++17
100 / 100
 4452 ms 1600504 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
//#include "grader.cpp"

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll bucksize=200;
ll sol[200005];
ll cap[200005];
vector<ll> toprop[10005];
ll n;
ll v[200005];
ll s[200005];
ll sufmin[200005],sufmax[200005];
ll getbuck(ll x)
{
    return x/bucksize;
}
ll q;
vector<pll> ord;
void solve(ll poz)
{
    sort(ord.begin(),ord.end());
    if(poz+1<=q&&s[sufmin[poz+1]]-s[poz]<0)
        poz=sufmin[poz+1];
    while(!ord.empty())
    {
        if(poz==q)
        {
            for(auto i:ord)
                sol[i.second]=0;
            ord.clear();
            break;
        }
        ll p=sufmax[poz+1];
        ll val=s[p]-s[poz];
        while(!ord.empty()&&ord.back().first>=val)
        {
            ll i=ord.back().second;
            sol[i]=s[q]-s[poz];
            ord.pop_back();
        }
        if(p==q)
        {
            for(auto i:ord)
                sol[i.second]=i.first;
            ord.clear();
            break;
        }
        while(!ord.empty())
        {
            ll i=ord.back().second;
            ll cc=ord.back().first;
            ll x=s[sufmin[p+1]]-s[poz]-(val-cc);
            if(x>=0)
            {
                sol[i]=s[q]-s[poz]-(val-cc);
                ord.pop_back();
            }
            else
                break;
        }
        poz=sufmin[p];
    }
}
void solve2(ll p)
{
    sort(ord.begin(),ord.end());
    ll poz=0;
    ll val=s[p]-s[poz];
    if(p==q)
    {
        for(auto i:ord)
            sol[i.second]=i.first;
        ord.clear();
        return;
    }
    while(!ord.empty())
    {
        ll i=ord.back().second;
        ll cc=ord.back().first;
        ll x=s[sufmin[p+1]]-s[poz]-(val-cc);
        if(x>=0)
        {
            sol[i]=s[q]-s[poz]-(val-cc);
            ord.pop_back();
        }
        else
            break;
    }
    poz=sufmin[p];
    while(!ord.empty())
    {
        if(poz==q)
        {
            for(auto i:ord)
                sol[i.second]=0;
            ord.clear();
            break;
        }
        ll p=sufmax[poz+1];
        ll val=s[p]-s[poz];
        while(!ord.empty()&&ord.back().first>=val)
        {
            ll i=ord.back().second;
            sol[i]=s[q]-s[poz];
            ord.pop_back();
        }
        if(p==q)
        {
            for(auto i:ord)
                sol[i.second]=i.first;
            ord.clear();
            break;
        }
        while(!ord.empty())
        {
            ll i=ord.back().second;
            ll cc=ord.back().first;
            ll x=s[sufmin[p+1]]-s[poz]-(val-cc);
            if(x>=0)
            {
                sol[i]=s[q]-s[poz]-(val-cc);
                ord.pop_back();
            }
            else
                break;
        }
        poz=sufmin[p];
    }
}
bool use[200005];
void prop(ll buck)
{
    if(toprop[buck].empty())
        return;
    ll l=buck*bucksize;
    ll r=min(n-1,l+bucksize-1);
    for(int i=l;i<=r;i++)
        use[i]=0;
    q=toprop[buck].size();
    for(int i=0;i<q;i++)
        v[i+1]=toprop[buck][i];
    toprop[buck].clear();
    s[0]=0;
    for(int i=1;i<=q;i++)
        s[i]=s[i-1]+v[i];
    sufmin[q]=q;
    sufmax[q]=q;
    for(int i=q-1;i>=1;i--)
    {
        sufmax[i]=sufmax[i+1];
        sufmin[i]=sufmin[i+1];
        if(s[i]>s[sufmax[i]])
            sufmax[i]=i;
        if(s[i]<s[sufmin[i]])
            sufmin[i]=i;
    }
    ord.clear();
    for(int i=l;i<=r;i++)
        if(!use[i]&&sol[i]+s[sufmin[1]]<=0)
        {
            use[i]=1;
            ord.push_back({cap[i],i});
        }
    solve(sufmin[1]);

    ord.clear();
    for(int i=l;i<=r;i++)
        if(!use[i]&&sol[i]+s[sufmax[1]]<=cap[i])
        {
            use[i]=1;
            sol[i]+=s[q];
        }
    for(int i=l;i<=r;i++)
        if(!use[i])
        {
            use[i]=1;
            ord.push_back({cap[i],i});
        }
    solve2(sufmax[1]);
}
void plsadd(ll l,ll r,ll val)
{
    ll b1=getbuck(l);
    ll b2=getbuck(r);
    for(ll i=b1+1;i<b2;i++)
        toprop[i].push_back(val);
    prop(b1);
    prop(b2);
    for(ll i=l;i<=r&&getbuck(i)==b1;i++)
    {
        sol[i]+=val;
        if(sol[i]<0)
            sol[i]=0;
        if(sol[i]>cap[i])
            sol[i]=cap[i];
    }
    if(b1!=b2)
    {
        for(ll i=r;i>=l&&getbuck(i)==b2;i--)
        {
            sol[i]+=val;
            if(sol[i]<0)
                sol[i]=0;
            if(sol[i]>cap[i])
                sol[i]=cap[i];
        }
    }
}
ll mars[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v)
{
    n=c.size();
    for(int i=0;i<c.size();i++)
        cap[i]=c[i];
    bool ok=1;
    for(int i=0;i<v.size();i++)
        if(v[i]<0)
            ok=0;
    if(ok)
    {
        for(ll i=0;i<l.size();i++)
        {
            ll st=l[i];
            ll dr=r[i];
            ll val=v[i];
            mars[st]+=val;
            mars[dr+1]-=val;
        }
        ll suma=0;
        vector<int> ans;
        for(ll i=0;i<n;i++)
        {
            suma+=mars[i];
            sol[i]=min(suma,cap[i]);
            ans.push_back(sol[i]);
        }
        return ans;
    }
    for(int i=0;i<l.size();i++)
    {
        ll st=l[i];
        ll dr=r[i];
        ll val=v[i];
        plsadd(st,dr,val);
    }
    for(ll b=0;bucksize*b<n;b++)
        prop(b);
    vector<int> ans;
    for(int i=0;i<n;i++)
        ans.push_back(sol[i]);
    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:217:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |     for(int i=0;i<c.size();i++)
      |                 ~^~~~~~~~~
candies.cpp:220:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
candies.cpp:225:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |         for(ll i=0;i<l.size();i++)
      |                    ~^~~~~~~~~
candies.cpp:243:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 16 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 12824 KB Output is correct
2 Correct 94 ms 12632 KB Output is correct
3 Correct 82 ms 12640 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 192 ms 5604 KB Output is correct
3 Correct 58 ms 11720 KB Output is correct
4 Correct 962 ms 24524 KB Output is correct
5 Correct 1050 ms 24304 KB Output is correct
6 Correct 2427 ms 24636 KB Output is correct
7 Correct 2425 ms 24376 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 258 ms 24520 KB Output is correct
4 Correct 73 ms 22852 KB Output is correct
5 Correct 3950 ms 1600504 KB Output is correct
6 Correct 3747 ms 1600204 KB Output is correct
7 Correct 3715 ms 1600196 KB Output is correct
8 Correct 3733 ms 1600192 KB Output is correct
9 Correct 83 ms 10840 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 16 ms 724 KB Output is correct
6 Correct 88 ms 12824 KB Output is correct
7 Correct 94 ms 12632 KB Output is correct
8 Correct 82 ms 12640 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 192 ms 5604 KB Output is correct
11 Correct 58 ms 11720 KB Output is correct
12 Correct 962 ms 24524 KB Output is correct
13 Correct 1050 ms 24304 KB Output is correct
14 Correct 2427 ms 24636 KB Output is correct
15 Correct 2425 ms 24376 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 258 ms 24520 KB Output is correct
19 Correct 73 ms 22852 KB Output is correct
20 Correct 3950 ms 1600504 KB Output is correct
21 Correct 3747 ms 1600204 KB Output is correct
22 Correct 3715 ms 1600196 KB Output is correct
23 Correct 3733 ms 1600192 KB Output is correct
24 Correct 83 ms 10840 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 84 ms 11304 KB Output is correct
27 Correct 954 ms 7248 KB Output is correct
28 Correct 3033 ms 27944 KB Output is correct
29 Correct 3763 ms 24344 KB Output is correct
30 Correct 4109 ms 29308 KB Output is correct
31 Correct 4335 ms 29676 KB Output is correct
32 Correct 4452 ms 29832 KB Output is correct