oj.uz

Submission #839107

# Submission time Handle Problem Language Result Execution time Memory
839107 2023-08-28T16:16:50 Z andrei_boaca Distributing Candies (IOI21_candies) C++17
100 / 100
 4469 ms 1600380 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: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++)
      |                 ~^~~~~~~~~
candies.cpp:219:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  219 |     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 564 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 16 ms 732 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4333 ms 24780 KB Output is correct
2 Correct 4025 ms 28052 KB Output is correct
3 Correct 3694 ms 28084 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 198 ms 5608 KB Output is correct
3 Correct 65 ms 11644 KB Output is correct
4 Correct 957 ms 24484 KB Output is correct
5 Correct 1055 ms 24308 KB Output is correct
6 Correct 2341 ms 24656 KB Output is correct
7 Correct 2465 ms 24528 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 556 KB Output is correct
3 Correct 264 ms 24408 KB Output is correct
4 Correct 81 ms 22904 KB Output is correct
5 Correct 3851 ms 1600316 KB Output is correct
6 Correct 3680 ms 1600216 KB Output is correct
7 Correct 3587 ms 1600328 KB Output is correct
8 Correct 3607 ms 1600184 KB Output is correct
9 Correct 3538 ms 1600380 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 564 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 16 ms 732 KB Output is correct
6 Correct 4333 ms 24780 KB Output is correct
7 Correct 4025 ms 28052 KB Output is correct
8 Correct 3694 ms 28084 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 198 ms 5608 KB Output is correct
11 Correct 65 ms 11644 KB Output is correct
12 Correct 957 ms 24484 KB Output is correct
13 Correct 1055 ms 24308 KB Output is correct
14 Correct 2341 ms 24656 KB Output is correct
15 Correct 2465 ms 24528 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 556 KB Output is correct
18 Correct 264 ms 24408 KB Output is correct
19 Correct 81 ms 22904 KB Output is correct
20 Correct 3851 ms 1600316 KB Output is correct
21 Correct 3680 ms 1600216 KB Output is correct
22 Correct 3587 ms 1600328 KB Output is correct
23 Correct 3607 ms 1600184 KB Output is correct
24 Correct 3538 ms 1600380 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 81 ms 10804 KB Output is correct
27 Correct 958 ms 5352 KB Output is correct
28 Correct 2974 ms 24088 KB Output is correct
29 Correct 3755 ms 24336 KB Output is correct
30 Correct 4011 ms 24120 KB Output is correct
31 Correct 4315 ms 24220 KB Output is correct
32 Correct 4469 ms 24288 KB Output is correct