oj.uz

Submission #436964

# Submission time Handle Problem Language Result Execution time Memory
436964 2021-06-25T11:55:44 Z omohamadooo Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 10708 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=3e5;

ll seg[N];
vector<int>ans(N);
vector<int>tmm;
vector<int>c;

void push(ll v,ll l,ll r)
{
    ll m=(l+r)/2;
    if(l==m){
        ans[l]+=seg[v];
        if(ans[l]>c[l]) ans[l]=c[l];
        if(ans[l]<0) ans[l]=0;
        if(r==m+1){
            ans[r]+=seg[v];
            if(ans[r]>c[r]) ans[r]=c[r];
            if(ans[r]<0) ans[r]=0;
        }
        seg[v]=0;
        return;
    }
    if(r==m+1){
        ans[r]+=seg[v];
        if(ans[r]>c[r]) ans[r]=c[r];
        if(ans[r]<0) ans[r]=0;
        if(seg[v*2+1]) push(v*2+1,l,m);
        seg[v*2+1]=seg[v];
        seg[v]=0;
        return;
    }
    if(seg[v*2+1]) push(v*2+1,l,m);
    if(seg[v*2+2]) push(v*2+2,m+1,r);
    seg[v*2+1]=seg[v];
    seg[v*2+2]=seg[v];
    seg[v]=0;
    return;
}

void upd(ll v,ll segl,ll segr,ll l,ll r,ll val)
{
    if(segl>r||segr<l) return;
    if(segl>=l&&segr<=r){
        if(segl==segr){
            ans[segl]+=val;
            if(ans[segl]>c[segl]) ans[segl]=c[segl];
            if(ans[segl]<0) ans[segl]=0;
        }
        else{
            if(seg[v]) push(v,segl,segr);
            seg[v]=val;
        }
        return;
    }
    if(seg[v]) push(v,segl,segr);
    ll m=(segl+segr)/2;
    upd(v*2+1,segl,m,l,r,val);
    upd(v*2+2,m+1,segr,l,r,val);
}

void get(ll v,ll l,ll r,ll pos)
{
    if(l==r) return ;
    if(seg[v]) tmm.pb(seg[v]);
    ll m=(l+r)/2;
    if(m>=pos) get(v*2+1,l,m,pos);
    else get(v*2+2,m+1,r,pos);
}

vector<int> distribute_candies(vector<int>C, vector<int> l, vector<int> r, vector<int> v)
{
    ll n=C.size();
    for(ll i=0;i<C.size();i++) c.pb(C[i]);
    for(ll i=0;i<l.size();i++)
        upd(0,0,n-1,l[i],r[i],v[i]);
    for(ll i=0;i<c.size();i++){
        get(0,0,n-1,i);
        reverse(tmm.begin(),tmm.end());
        for(ll j=0;j<tmm.size();j++){
            if(ans[i]+tmm[j]>c[i]) ans[i]=c[i];
            else if(ans[i]+tmm[j]<0) ans[i]=0;
            else ans[i]+=tmm[j];
        }
        tmm.clear();
    }
    while(ans.size()>c.size()) ans.pop_back();
    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:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(ll i=0;i<C.size();i++) c.pb(C[i]);
      |                ~^~~~~~~~~
candies.cpp:78:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(ll i=0;i<l.size();i++)
      |                ~^~~~~~~~~
candies.cpp:80:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(ll i=0;i<c.size();i++){
      |                ~^~~~~~~~~
candies.cpp:83:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(ll j=0;j<tmm.size();j++){
      |                    ~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 31 ms 1560 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1332 ms 6228 KB Output is correct
3 Correct 1311 ms 7948 KB Output is correct
4 Execution timed out 5063 ms 10704 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1484 KB Output is correct
2 Correct 6 ms 1484 KB Output is correct
3 Correct 4051 ms 6224 KB Output is correct
4 Correct 4309 ms 6948 KB Output is correct
5 Execution timed out 5070 ms 10604 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 31 ms 1560 KB Output is correct
6 Execution timed out 5041 ms 10708 KB Time limit exceeded
7 Halted 0 ms 0 KB -