oj.uz

Submission #614144

# Submission time Handle Problem Language Result Execution time Memory
614144 2022-07-30T19:59:26 Z krit3379 Distributing Candies (IOI21_candies) C++17
3 / 100
 147 ms 43988 KB 
#include<bits/stdc++.h>
#include"candies.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 200005

struct SegmentTree{
    int n,ll,rr;
    long long mi[4*N],ma[4*N],lazy[4*N],val;
    void init(int _n){
        n=_n;
        for(int i=0;i<4*N;i++)mi[4*N]=ma[4*N]=lazy[4*N]=0;
    }
    void push(int x){
        if(lazy[x]){
            lazy[x*2]+=lazy[x];
            lazy[x*2+1]+=lazy[x];
            mi[x]+=lazy[x];
            ma[x]+=lazy[x];
            lazy[x]=0;
        }
    }
    void upd(int x,int l,int r){
        push(x);
        if(l>rr||ll>r)return ;
        if(ll<=l&&r<=rr){
            lazy[x]+=val;
            push(x);
            return ;
        }
        int mid=(l+r)/2;
        upd(x*2,l,mid);
        upd(x*2+1,mid+1,r);
        mi[x]=min(mi[x*2],mi[x*2+1]);
        ma[x]=max(ma[x*2],ma[x*2+1]);
    }
    void upd(int x,long long v){
        ll=x,rr=n,val=v;
        upd(1,1,n);
    }
    long long min_val(int x,int l,int r,int p){
        push(x);
        if(p>r)return 1e18;
        if(l>=p)return mi[x];
        int mid=(l+r)/2;
        return min(min_val(x*2,l,mid,p),min_val(x*2+1,mid+1,r,p));
    }
    long long min_val(int x){
        return min_val(1,1,n,x);
    }
    long long max_val(int x,int l,int r,int p){
        push(x);
        if(p>r)return -1e18;
        if(l>=p)return ma[x];
        int mid=(l+r)/2;
        return max(max_val(x*2,l,mid,p),max_val(x*2+1,mid+1,r,p));
    }
    long long max_val(int x){
        return max_val(1,1,n,x);
    }
    long long point_val(int x,int l,int r,int p){
        push(x);
        if(l>p||p>r)return 0;
        if(l==r)return ma[x];
        int mid=(l+r)/2;
        return point_val(x*2,l,mid,p)+point_val(x*2+1,mid+1,r,p);
    }
    long long point_val(int x){
        return point_val(1,1,n,x);
    }


}st;

vector<int> ans;
vector<pair<int,int>> op[N];

vector<int> distribute_candies(vector<int> C,vector<int> L,vector<int> R,vector<int> V){
    int n=C.size(),q=L.size(),i,l,r,mid,pos;
    ans.resize(n);
    for(i=0;i<q;i++){
        op[L[i]].push_back({i+2,V[i]});
        op[R[i]+1].push_back({i+2,-V[i]});
    }
    st.init(q+1);
    for(i=0;i<n;i++){
        for(auto [x,v]:op[i])st.upd(x,v);
        long long m1=st.max_val(0),m2=st.min_val(0);
        if(m1-m2<C[i]){
            ans[i]=st.max_val(q+1)-m2;
            continue;
        }
        l=0,r=q+1;
        while(l<=r){
            mid=(l+r)/2;
            m1=st.max_val(mid),m2=st.min_val(mid);
            if(m1-m2>=C[i])pos=mid,l=mid+1;
            else r=mid-1;
        }
        long long v1=st.point_val(pos),v2=st.max_val(q+1);
        m1=st.max_val(pos),m2=st.min_val(pos);
        if(v1==m1)ans[i]=v2-m2;
        else ans[i]=C[i]-(m1-v2);
    }
    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:13:55: warning: array subscript 800020 is above array bounds of 'long long int [800020]' [-Warray-bounds]
   13 |         for(int i=0;i<4*N;i++)mi[4*N]=ma[4*N]=lazy[4*N]=0;
      |                                               ~~~~~~~~^
candies.cpp:10:31: note: while referencing 'SegmentTree::lazy'
   10 |     long long mi[4*N],ma[4*N],lazy[4*N],val;
      |                               ^~~~
candies.cpp:13:45: warning: array subscript 800020 is above array bounds of 'long long int [800020]' [-Warray-bounds]
   13 |         for(int i=0;i<4*N;i++)mi[4*N]=ma[4*N]=lazy[4*N]=0;
      |                                       ~~~~~~^
candies.cpp:10:23: note: while referencing 'SegmentTree::ma'
   10 |     long long mi[4*N],ma[4*N],lazy[4*N],val;
      |                       ^~
candies.cpp:13:37: warning: array subscript 800020 is above array bounds of 'long long int [800020]' [-Warray-bounds]
   13 |         for(int i=0;i<4*N;i++)mi[4*N]=ma[4*N]=lazy[4*N]=0;
      |                               ~~~~~~^
candies.cpp:10:15: note: while referencing 'SegmentTree::mi'
   10 |     long long mi[4*N],ma[4*N],lazy[4*N],val;
      |               ^~
candies.cpp:44:9: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |         if(p>r)return 1e18;
      |         ^~
candies.cpp:80:41: note: 'pos' was declared here
   80 |     int n=C.size(),q=L.size(),i,l,r,mid,pos;
      |                                         ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 8 ms 5204 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4988 KB Output is correct
2 Runtime error 81 ms 34116 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Runtime error 89 ms 43988 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 8 ms 5204 KB Output is correct
6 Runtime error 147 ms 39016 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -