Submission #836980

#	Time	Username	Problem	Language	Result	Execution time	Memory
836980		il9	Distributing Candies (IOI21_candies)	C++17	0 / 100	90 ms	55260 KiB

candies

#include "candies.h"
using namespace std;
using ll=long long;
#include <bits/stdc++.h>
vector<array<int,2> > seg(2000001);
vector<bool> segtrue(2000001);
vector<array<int,2> > li;
vector<int> flag(200001);
void build(int v, int tl, int tr){
    if(tl==tr){
        seg[v]=li[tl];
        segtrue[v]=1;
    }else{
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
    }
}
void push_flag(int v){
    if(flag[v]!=0){
        if(segtrue[v*2]){
            if(flag[v]>0){
                seg[v*2][0]=min(seg[v*2][0]+flag[v],seg[v*2][1]);
            }else{
                seg[v*2][0]=max(seg[v*2][0]+flag[v],0);
            }
        }else if(flag[v*2]>0){
            push_flag(v*2);
            flag[v*2]=flag[v];
        }
        if(segtrue[v*2+1]){
            if(flag[v]>0){
                seg[v*2+1][0]=min(seg[v*2+1][0]+flag[v],seg[v*2+1][1]);
            }else{
                seg[v*2+1][0]=max(seg[v*2+1][0]+flag[v],0);
            }
        }else if(flag[v*2+1]>0){
            push_flag(v*2+1);
            flag[v*2+1]=flag[v];
        }

    }
}
void update(int v, int tl, int tr, int l, int r, int x){
    push_flag(v);
    if(l==tl&&r==tr){
        flag[v]=x;
        return;
    }
}
int query(int v,int tl, int tr, int pos){
    if(tl==tr){
        return seg[v][0];
    }
    push_flag(v);
    int tm=(tl+tr)/2;
    if(pos<=tm){
        query(v*2,tl,tm,pos);
    }else{
        query(v*2+1,tm+1,tr,pos);
    }
}
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();
    
    for(int i=0;i<n;i++){
        li.push_back({0,c[i]});
    }
    for(int i=0;i<l.size();i++){
        update(1,0,n-1,l[i],r[i],v[i]);
    }
    vector<int> ans;
    for(int i=0;i<n;i++){
        ans.push_back(query(1,0,n-1,i));
    }
    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:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
candies.cpp: In function 'int query(int, int, int, int)':
candies.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33