제출 #801612

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

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
struct st{
    ll mn=0,mx=0;
};
ll n,q,sum[mxn],lazy[4*mxn],arr[mxn],tree2[mxn];
vector<int>start[mxn],finish[mxn];
st tree[mxn*4];
void update2(int idx,ll val){
    while(idx<=q){
        tree2[idx]+=val;
        idx+=(idx&(-idx));
    }
}
ll query2(int idx){
    ll ans=0;
    while(idx>0){
        ans+=tree2[idx];
        idx-=(idx&(-idx));
    }
    return ans;
}
void relax(int node,int l,int r){
    if(l!=r){
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    tree[node].mn+=lazy[node];
    tree[node].mx+=lazy[node];
    lazy[node]=0;
}
void update(int node,int l,int r,int ql,int qr,int val){
    if(lazy[node]){
        relax(node,l,r);
    }
    if(r<ql||l>qr) return;
    if(ql<=l&&r<=qr){
        lazy[node]=val;
        relax(node,l,r);
        return;
    }
    int m=(l+r)/2;
    update(2*node,l,m,ql,qr,val);
    update(2*node+1,m+1,r,ql,qr,val);
    tree[node].mn=min(tree[2*node].mn,tree[2*node+1].mn);
    tree[node].mx=max(tree[2*node].mx,tree[2*node+1].mx);
}
st query(int node,int l,int r,int ql,int qr){
    if(l>qr||r<ql){
        st ans;
        ans.mn=INF;
        ans.mx=-INF;
        return ans;
    }
    if(lazy[node]){
        relax(node,l,r);
    }
    if(ql<=l&&r<=qr){
        return tree[node];
    }
    int m=(l+r)/2;
    st x=query(2*node,l,m,ql,qr);
    st y=query(2*node+1,m+1,r,ql,qr);
    st ans;
    ans.mn=min(x.mn,y.mn);
    ans.mx=max(x.mx,y.mx);
    return ans;
}
vector<int> distribute_candies(vector<int> c, vector<int> x, vector<int> y, vector<int> vq) {
    n = c.size();
    q=x.size();
    int sz=q;  
    for(int i=0;i<q;i++){
        arr[i+1]=vq[i];
    }
    for(int i=0;i<q;i++){
        start[x[i]].pb(i);
        finish[y[i]+1].pb(i);
    }
    vector<int>ans;
    for(int id=0;id<n;id++){
        for(int v:start[id]){
            update(1,1,q,v+1,q,vq[v]);
            update2(v+1,vq[v]);
        }
        for(int v:finish[id]){
            update(1,1,q,v+1,q,-vq[v]);
            update2(v+1,-vq[v]);
        }
        int lim=c[id];
        int pos=0;
        int l=1,r=q;
        while(l<=r){
            int m=(l+r)/2;
            st res=query(1,1,q,m,q);
            if(res.mx-res.mn>lim){
                l=m+1;
            }
            else{
                r=m-1;
            }
        }
        pos=l-1;
        ll mxx=0,mnn=0,sum=0;
        if(pos>0){
            st res=query(1,1,q,pos,q);
            mxx=res.mx;
            mnn=res.mn;
            sum=query2(pos);
        }
        else{
            st res=query(1,1,q,1,q);
            mxx=max(res.mx,mxx);
            mnn=min(res.mn,mnn);
            sum=0;
        }
        if(mxx-sum>lim){
            ans.pb(lim-(mxx-query2(q)));
        }
        else{
            ans.pb(query2(q)-mnn);
        }
    }
    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:85:9: warning: unused variable 'sz' [-Wunused-variable]
   85 |     int sz=q;
      |         ^~

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