oj.uz

Submission #481146

# Submission time Handle Problem Language Result Execution time Memory
481146 2021-10-19T15:27:07 Z rumen_m Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 22260 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 2e6+2;
long long c[MAXN];
vector <int> ans;
long long MIN(long long a, long long b)
{
    if(a<b)return a;
    return b;
}
long long MAX(long long a, long long b)
{
    if(a>b)return a;
    return b;
}
struct Segment
{
    long long minel[MAXN],maxel[MAXN], lazy[MAXN];
    void update_lazy(long long v, long long from, long long to)
    {
        if(lazy[v]==0)return ;
        minel[2*v]+=lazy[v];
        maxel[2*v]+=lazy[v];
        minel[2*v+1]+=lazy[v];
        maxel[2*v+1]+=lazy[v];
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
        lazy[v] = 0;
    }
    void update(long long v,long long from, long long to, long long l, long long r, long long delta)
    {
          //  cout<<"UPDATE:: "<<v<<" "<<from<<" "<<to<<" "<<l<<" "<<r<<" "<<delta<<endl;
        if(from==to)
        {
            minel[v] = MAX((long long)0, MIN(c[from],minel[v]+delta));
            maxel[v] = MAX((long long)0, MIN(c[from],maxel[v]+delta));
        //    cout<<v<<" "<<minel[v]<<" "<<maxel[v]<<endl;
            return ;
        }
         update_lazy(v,from,to);
         long long mid = (from+to)/2;
        if(l<=from&&to<=r)
        {
            minel[v]+=delta;
            maxel[v]+=delta;
            if(minel[v]<0||maxel[v]>c[0])
            {
                update(2*v,from,mid,l,r,delta);
                update(2*v+1,mid+1,to,l,r,delta);
                minel[v] = MIN(minel[2*v],minel[2*v+1]);
                maxel[v] = MAX(maxel[2*v],maxel[2*v+1]);
            }
            else
                lazy[v]+=delta;
            return ;
        }
        if(l<=mid)
        update(2*v,from,mid,l,r,delta);
        if(r>mid)
        update(2*v+1,mid+1,to,l,r,delta);
        minel[v] = MIN(minel[2*v],minel[2*v+1]);
                maxel[v] = MAX(maxel[2*v],maxel[2*v+1]);
               // cout<<v<<" "<<minel[v]<<" "<<maxel[v]<<endl;
    }
    void query(long long v, long long from, long long to)
    {
        if(from==to)
        {
         //  cout<<"-> "<<from<<" "<<minel[v]<<endl;
            ans[from] =  minel[v];
            return ;
        }
        long long mid = (from+to)/2;
        update_lazy(v,from,to);
        query(2*v,from,mid);
        query(2*v+1,mid+1,to);
    }
};
Segment S;
std::vector<int> distribute_candies(std::vector<int> _c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    int n = _c.size();
    int i,j;
    for(i = 0; i<n;i++)
        c[i] = _c[i];
    for(i=0;i<l.size();i++)
    {
        S.update(1,0,n-1,l[i],r[i],v[i]);
    }
    ans.resize(n);
    S.query(1,0,n-1);
    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:87:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(i=0;i<l.size();i++)
      |             ~^~~~~~~~~
candies.cpp:84:11: warning: unused variable 'j' [-Wunused-variable]
   84 |     int i,j;
      |           ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 332 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 5031 ms 20692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 150 ms 5148 KB Output is correct
3 Correct 133 ms 18480 KB Output is correct
4 Correct 907 ms 22260 KB Output is correct
5 Correct 2097 ms 22008 KB Output is correct
6 Execution timed out 5041 ms 20676 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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