oj.uz

답안 #839105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839105 2023-08-28T16:14:19 Z andrei_boaca 사탕 분배 (IOI21_candies) C++17
67 / 100
 5000 ms 1071852 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=300;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 19 ms 684 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12344 KB Output is correct
2 Correct 88 ms 12392 KB Output is correct
3 Correct 80 ms 12384 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 229 ms 5324 KB Output is correct
3 Correct 56 ms 9768 KB Output is correct
4 Correct 889 ms 17824 KB Output is correct
5 Correct 1030 ms 17636 KB Output is correct
6 Correct 3219 ms 17656 KB Output is correct
7 Correct 3168 ms 17792 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 245 ms 19500 KB Output is correct
4 Correct 65 ms 17380 KB Output is correct
5 Correct 2477 ms 1071592 KB Output is correct
6 Correct 2493 ms 1071816 KB Output is correct
7 Correct 2476 ms 1071820 KB Output is correct
8 Correct 2497 ms 1071852 KB Output is correct
9 Correct 81 ms 11048 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 19 ms 684 KB Output is correct
6 Correct 83 ms 12344 KB Output is correct
7 Correct 88 ms 12392 KB Output is correct
8 Correct 80 ms 12384 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 229 ms 5324 KB Output is correct
11 Correct 56 ms 9768 KB Output is correct
12 Correct 889 ms 17824 KB Output is correct
13 Correct 1030 ms 17636 KB Output is correct
14 Correct 3219 ms 17656 KB Output is correct
15 Correct 3168 ms 17792 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 245 ms 19500 KB Output is correct
19 Correct 65 ms 17380 KB Output is correct
20 Correct 2477 ms 1071592 KB Output is correct
21 Correct 2493 ms 1071816 KB Output is correct
22 Correct 2476 ms 1071820 KB Output is correct
23 Correct 2497 ms 1071852 KB Output is correct
24 Correct 81 ms 11048 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 97 ms 9720 KB Output is correct
27 Correct 1113 ms 6220 KB Output is correct
28 Correct 3968 ms 18644 KB Output is correct
29 Execution timed out 5067 ms 21476 KB Time limit exceeded
30 Halted 0 ms 0 KB -