oj.uz

답안 #839104

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839104 2023-08-28T16:13:18 Z andrei_boaca 사탕 분배 (IOI21_candies) C++17
40 / 100
 5000 ms 332300 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=1000;
ll sol[200005];
ll cap[200005];
vector<ll> toprop[455];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 12164 KB Output is correct
2 Correct 90 ms 12444 KB Output is correct
3 Correct 85 ms 12420 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 220 ms 5096 KB Output is correct
3 Correct 64 ms 7620 KB Output is correct
4 Correct 1435 ms 11812 KB Output is correct
5 Correct 1690 ms 11888 KB Output is correct
6 Execution timed out 5066 ms 10632 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1461 ms 5088 KB Output is correct
4 Correct 71 ms 9748 KB Output is correct
5 Correct 1888 ms 332248 KB Output is correct
6 Correct 2090 ms 332276 KB Output is correct
7 Correct 1440 ms 332300 KB Output is correct
8 Correct 1721 ms 332240 KB Output is correct
9 Correct 80 ms 10636 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 88 ms 12164 KB Output is correct
7 Correct 90 ms 12444 KB Output is correct
8 Correct 85 ms 12420 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 220 ms 5096 KB Output is correct
11 Correct 64 ms 7620 KB Output is correct
12 Correct 1435 ms 11812 KB Output is correct
13 Correct 1690 ms 11888 KB Output is correct
14 Execution timed out 5066 ms 10632 KB Time limit exceeded
15 Halted 0 ms 0 KB -