oj.uz

Submission #894805

# Submission time Handle Problem Language Result Execution time Memory
894805 2023-12-29T04:14:07 Z Muhammad_Aneeq Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 26964 KB 
#include <vector>
using namespace std;
int const N=2e5+10;
struct segt
{
    long long lazy=0,sp=0,fi=0;
};
segt St[4*N]={};
long long a[N]={};
void build(int i,int st,int en)
{
    if (st==en)
    {
        St[i].sp=a[st];
        St[i].fi=0;
        return;
    }
    int mid=(st+en)/2;
    build(i*2,st,mid);build(i*2+1,mid+1,en);
    St[i].sp=min(St[i*2].sp,St[i*2+1].sp);
    St[i].fi=max(St[i*2].fi,St[i*2+1].fi);
}
bool w=0;
void update(int i,int st,int en,int l,int r,long long val)
{
    if (st>r||en<l)
        return;
    if (st>=l&&en<=r&&st==en)
    {
        St[i].sp=min(a[st],max(St[i].sp-val,0LL));
        St[i].fi=min(a[st],max(St[i].fi+val,0LL));
        return;
    }
    if (st>=l&&en<=r&&St[i].sp-val>=0&&St[i].fi+val>=0)
    {
        St[i].sp+=val;
        St[i].fi+=val;
        St[i].lazy+=val;
        return;
    }
    int mid=(st+en)/2;
    update(i*2,st,mid,l,r,val+St[i].lazy);update(i*2+1,mid+1,en,l,r,val+St[i].lazy);
    St[i].lazy=0;
    St[i].sp=min(St[i*2].sp,St[i*2+1].sp);
    St[i].fi=max(St[i*2].fi,St[i*2+1].fi);
}
void update1(int i,int st,int en,long long val)
{
    if (st==en)
    {   
        St[i].sp=min(a[st],max(St[i].sp-val,0LL));
        St[i].fi=min(a[st],max(St[i].fi+val,0LL));
        return;
    }
    int mid=(st+en)/2;
    update1(i*2,st,mid,val+St[i].lazy);update1(i*2+1,mid+1,en,val+St[i].lazy);
}
int get(int i,int st,int en,int r)
{
    if (st==en)
        return St[i].fi;
    int mid=(st+en)/2;
    if (r<=mid)
        return get(i*2,st,mid,r);
    return get(i*2+1,mid+1,en,r);
}
int n;
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v)
{
    n=c.size();
    for (int i=0;i<n;i++)
        a[i]=c[i];
    build(1,0,n-1);
    for (int i=0;i<l.size();i++)
        update(1,0,n-1,l[i],r[i],v[i]);
    w=1;
    update1(1,0,n-1,0);
    vector<int>ans;
    for (int i=0;i<n;i++)
        ans.push_back(get(1,0,n-1,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:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i=0;i<l.size();i++)
      |                  ~^~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2648 KB Output is correct
3 Incorrect 2 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 26964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2648 KB Output is correct
3 Incorrect 2 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -