oj.uz

Submission #614151

# Submission time Handle Problem Language Result Execution time Memory
614151 2022-07-30T20:09:03 Z krit3379 Distributing Candies (IOI21_candies) C++17
100 / 100
 1584 ms 45328 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[i]=ma[i]=lazy[i]=0;
    }
    void push(int x){
        if(lazy[x]){
            if(x<2*N){
                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:46:9: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |         if(p>r)return 1e18;
      |         ^~
candies.cpp:82:41: note: 'pos' was declared here
   82 |     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 11 ms 23764 KB Output is correct
2 Correct 11 ms 23684 KB Output is correct
3 Correct 11 ms 23876 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 16 ms 23832 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1584 ms 38692 KB Output is correct
2 Correct 1352 ms 42704 KB Output is correct
3 Correct 1312 ms 42540 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23784 KB Output is correct
2 Correct 207 ms 32984 KB Output is correct
3 Correct 302 ms 30356 KB Output is correct
4 Correct 1077 ms 44552 KB Output is correct
5 Correct 1276 ms 44948 KB Output is correct
6 Correct 1304 ms 45328 KB Output is correct
7 Correct 1311 ms 44672 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 104 ms 31704 KB Output is correct
4 Correct 370 ms 28324 KB Output is correct
5 Correct 740 ms 38172 KB Output is correct
6 Correct 853 ms 38888 KB Output is correct
7 Correct 994 ms 39464 KB Output is correct
8 Correct 701 ms 38180 KB Output is correct
9 Correct 760 ms 39668 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23684 KB Output is correct
3 Correct 11 ms 23876 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 16 ms 23832 KB Output is correct
6 Correct 1584 ms 38692 KB Output is correct
7 Correct 1352 ms 42704 KB Output is correct
8 Correct 1312 ms 42540 KB Output is correct
9 Correct 10 ms 23784 KB Output is correct
10 Correct 207 ms 32984 KB Output is correct
11 Correct 302 ms 30356 KB Output is correct
12 Correct 1077 ms 44552 KB Output is correct
13 Correct 1276 ms 44948 KB Output is correct
14 Correct 1304 ms 45328 KB Output is correct
15 Correct 1311 ms 44672 KB Output is correct
16 Correct 10 ms 23764 KB Output is correct
17 Correct 10 ms 23764 KB Output is correct
18 Correct 104 ms 31704 KB Output is correct
19 Correct 370 ms 28324 KB Output is correct
20 Correct 740 ms 38172 KB Output is correct
21 Correct 853 ms 38888 KB Output is correct
22 Correct 994 ms 39464 KB Output is correct
23 Correct 701 ms 38180 KB Output is correct
24 Correct 760 ms 39668 KB Output is correct
25 Correct 11 ms 23764 KB Output is correct
26 Correct 243 ms 28268 KB Output is correct
27 Correct 196 ms 35516 KB Output is correct
28 Correct 1014 ms 43200 KB Output is correct
29 Correct 1184 ms 43576 KB Output is correct
30 Correct 1335 ms 43768 KB Output is correct
31 Correct 1366 ms 43908 KB Output is correct
32 Correct 1314 ms 44164 KB Output is correct