oj.uz

Submission #836983

# Submission time Handle Problem Language Result Execution time Memory
836983 2023-08-24T19:11:18 Z il9 Distributing Candies (IOI21_candies) C++17
0 / 100
 93 ms 50392 KB 
#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 tm=(tl+tr)/2;
    update(v*2,tl,tm,l,min(r,tm),x);
    update(v*2+1,tm+1,tr,max(l,tm+1),r,x);
}
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]});
    }
    build(1,0,n-1);
    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

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
candies.cpp: In function 'int query(int, int, int, int)':
candies.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 34236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 50392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 34256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 34260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 34236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -