제출 #614151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614151		krit3379	사탕 분배 (IOI21_candies)	C++17	100 / 100	1584 ms	45328 KiB

candies

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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