Submission #436964

#	Time	Username	Problem	Language	Result	Execution time	Memory
436964		omohamadooo	Distributing Candies (IOI21_candies)	C++17	3 / 100	5070 ms	10708 KiB

candies

#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 (stderr)

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 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33