oj.uz

Submission #839111

# Submission time Handle Problem Language Result Execution time Memory
839111 2023-08-28T16:30:36 Z andrei_boaca Distributing Candies (IOI21_candies) C++17
100 / 100
 4469 ms 1600568 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)
{
    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)
{
    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;
    }
    solve(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});
        }
    sort(ord.begin(),ord.end());
    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});
        }
    sort(ord.begin(),ord.end());
    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;
    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:178:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int i=0;i<c.size();i++)
      |                 ~^~~~~~~~~
candies.cpp:181:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
candies.cpp:184:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
candies.cpp:180:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  180 |     bool ok=1;
      |          ^~

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 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 17 ms 624 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4309 ms 24940 KB Output is correct
2 Correct 3998 ms 24540 KB Output is correct
3 Correct 3644 ms 24668 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 220 ms 5600 KB Output is correct
3 Correct 58 ms 11872 KB Output is correct
4 Correct 972 ms 24752 KB Output is correct
5 Correct 1097 ms 24572 KB Output is correct
6 Correct 2500 ms 24808 KB Output is correct
7 Correct 2595 ms 24680 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 267 ms 24460 KB Output is correct
4 Correct 75 ms 22904 KB Output is correct
5 Correct 3755 ms 1600244 KB Output is correct
6 Correct 3598 ms 1600568 KB Output is correct
7 Correct 3555 ms 1600540 KB Output is correct
8 Correct 3575 ms 1600364 KB Output is correct
9 Correct 3618 ms 1600396 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 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 17 ms 624 KB Output is correct
6 Correct 4309 ms 24940 KB Output is correct
7 Correct 3998 ms 24540 KB Output is correct
8 Correct 3644 ms 24668 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 220 ms 5600 KB Output is correct
11 Correct 58 ms 11872 KB Output is correct
12 Correct 972 ms 24752 KB Output is correct
13 Correct 1097 ms 24572 KB Output is correct
14 Correct 2500 ms 24808 KB Output is correct
15 Correct 2595 ms 24680 KB Output is correct
16 Correct 1 ms 564 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 267 ms 24460 KB Output is correct
19 Correct 75 ms 22904 KB Output is correct
20 Correct 3755 ms 1600244 KB Output is correct
21 Correct 3598 ms 1600568 KB Output is correct
22 Correct 3555 ms 1600540 KB Output is correct
23 Correct 3575 ms 1600364 KB Output is correct
24 Correct 3618 ms 1600396 KB Output is correct
25 Correct 1 ms 556 KB Output is correct
26 Correct 85 ms 10932 KB Output is correct
27 Correct 963 ms 5480 KB Output is correct
28 Correct 3000 ms 24400 KB Output is correct
29 Correct 3717 ms 24564 KB Output is correct
30 Correct 3953 ms 24192 KB Output is correct
31 Correct 4243 ms 24176 KB Output is correct
32 Correct 4469 ms 24276 KB Output is correct