제출 #853166

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

candies

#include "candies.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair <int, int> pll;
int n,q;
vector <int32_t> ve[200001],res;
int lazy[900001],pos;
pll st[900001];
pll combine(pll a, pll b){
    return {min(a.first,b.first),max(a.second,b.second)};
}
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    st[node<<1].first+=lazy[node];
    st[node<<1].second+=lazy[node];
    lazy[node<<1]+=lazy[node];
    st[node<<1|1].first+=lazy[node];
    st[node<<1|1].second+=lazy[node];
    lazy[node<<1|1]+=lazy[node];
    lazy[node]=0;
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        st[node].first+=val;
        st[node].second+=val;
        lazy[node]+=val;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=combine(st[node<<1],st[node<<1|1]);
}
pll get(int node, int l, int r, int u, int v){
    if (l>v||r<u|l>r||u>v)
        return {1e18,-1e18};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return combine(get(node<<1,l,mid,u,v),get(node<<1|1,mid+1,r,u,v));
}
vector <int32_t> distribute_candies(vector <int32_t> c, vector <int32_t> l, vector <int32_t> r, vector <int32_t> v){
    n=c.size();
    q=l.size();
    update(1,0,q+1,0,q+1,1e18);
    update(1,0,q+1,1,q+1,-1e18);
    for (int i=0;i<q;i++){
        ve[l[i]].push_back(i+1);
        ve[r[i]+1].push_back(-i-1);
    }
    for (int i=0;i<n;i++){
        for (int j:ve[i]){
            pos+=(j>0?v[j-1]:-v[-j-1]);
            update(1,0,q+1,abs(j)+1,q+1,(j>0?v[j-1]:-v[-j-1]));
        }
        int l=0,r=q+1;
        int kq=-1;
        while (l<=r){
            int mid=(l+r)>>1;
            auto [mn,mx]=get(1,0,q+1,mid,q+1);
            if (mx-mn>=c[i]){
                kq=(mid&&v[mid-1]>0?c[i]-mx+pos:pos-mn);
                l=mid+1;
            }
            else
                r=mid-1;
        }
        res.push_back(kq);
    }
    return res;
}

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

candies.cpp: In function 'pll get(long long int, long long int, long long int, long long int, long long int)':
candies.cpp:40:15: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   40 |     if (l>v||r<u|l>r||u>v)
      |              ~^~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33