oj.uz

답안 #614149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
614149 2022-07-30T20:03:17 Z krit3379 사탕 분배 (IOI21_candies) C++17
3 / 100
 166 ms 76488 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<4*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

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23732 KB Output is correct
3 Correct 11 ms 23828 KB Output is correct
4 Correct 13 ms 23904 KB Output is correct
5 Correct 17 ms 23892 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 166 ms 76488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Runtime error 95 ms 66580 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 11 ms 23772 KB Output is correct
3 Runtime error 104 ms 64220 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23732 KB Output is correct
3 Correct 11 ms 23828 KB Output is correct
4 Correct 13 ms 23904 KB Output is correct
5 Correct 17 ms 23892 KB Output is correct
6 Runtime error 166 ms 76488 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -