oj.uz

Submission #824805

# Submission time Handle Problem Language Result Execution time Memory
824805 2023-08-14T10:34:51 Z andrei_boaca Distributing Candies (IOI21_candies) C++17
40 / 100
 106 ms 22308 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;
int n,q;
vector<ll> v;
vector<int> sol;
ll s[200005];
vector<pll> ord;
ll sufmin[200005],sufmax[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> stanga,std::vector<int> dreapta, std::vector<int> vals)
{
    n = c.size();
    q=stanga.size();
    v.resize(n);
    sol.resize(n);
    if(n<=2000&&q<=2000)
    {
        for(int z=0;z<stanga.size();z++)
        {
            int l=stanga[z];
            int r=dreapta[z];
            int val=vals[z];
            for(int i=l;i<=r;i++)
            {
                v[i]+=val;
                if(v[i]<0)
                    v[i]=0;
                if(v[i]>c[i])
                    v[i]=c[i];
            }
        }
        for(int i=0;i<v.size();i++)
            sol[i]=v[i];
        return sol;
    }
    bool ok=1;
    for(int i=0;i<vals.size();i++)
        if(vals[i]<0)
            ok=0;
    if(ok)
    {
        for(int z=0;z<vals.size();z++)
        {
            int l=stanga[z];
            int r=dreapta[z];
            int val=vals[z];
            v[l]+=val;
            if(r+1<n)
                v[r+1]-=val;
        }
        ll suma=0;
        for(int i=0;i<n;i++)
        {
            suma+=v[i];
            sol[i]=min(suma,1LL*c[i]);
        }
        return sol;
    }
    ok=1;
    for(int i=0;i<vals.size();i++)
        if(stanga[i]!=0||dreapta[i]!=n-1)
            ok=0;
    if(ok)
    {
        for(int i=0;i<n;i++)
            ord.push_back({c[i],i});
        sort(ord.begin(),ord.end());
        for(int i=0;i<vals.size();i++)
            s[i+1]=vals[i];
        for(int i=1;i<=q;i++)
            s[i]=s[i-1]+s[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;
        }
        ll poz=0;
        if(s[sufmin[1]]<0)
            poz=sufmin[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];
        }
        return sol;
    }
    return sol;
}

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:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int z=0;z<stanga.size();z++)
      |                     ~^~~~~~~~~~~~~~
candies.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~
candies.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
candies.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int z=0;z<vals.size();z++)
      |                     ~^~~~~~~~~~~~
candies.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
candies.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=0;i<vals.size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 9596 KB Output is correct
2 Correct 77 ms 9720 KB Output is correct
3 Correct 77 ms 9676 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 40 ms 4980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 45 ms 9684 KB Output is correct
4 Correct 57 ms 9668 KB Output is correct
5 Correct 106 ms 20984 KB Output is correct
6 Correct 106 ms 21728 KB Output is correct
7 Correct 105 ms 22308 KB Output is correct
8 Correct 100 ms 20872 KB Output is correct
9 Correct 94 ms 14592 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 82 ms 9596 KB Output is correct
7 Correct 77 ms 9720 KB Output is correct
8 Correct 77 ms 9676 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Incorrect 40 ms 4980 KB Output isn't correct
11 Halted 0 ms 0 KB -