oj.uz

Submission #481145

# Submission time Handle Problem Language Result Execution time Memory
481145 2021-10-19T15:25:02 Z rumen_m Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 27272 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;
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:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(i=0;i<l.size();i++)
      |             ~^~~~~~~~~
candies.cpp:74:11: warning: unused variable 'j' [-Wunused-variable]
   74 |     int i,j;
      |           ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 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 5068 ms 25332 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 141 ms 8164 KB Output is correct
3 Correct 117 ms 20644 KB Output is correct
4 Correct 992 ms 27272 KB Output is correct
5 Correct 1980 ms 27148 KB Output is correct
6 Execution timed out 5092 ms 25668 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 3717 ms 7780 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 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -