제출 #443166

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

candies

#include <iostream>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef pair<int,int>pp;
typedef long long ll;
const int MAXN=200000;
int n,q;
ll sum,maxs[1<<19],mins[1<<19],lazy[1<<19];
vector<pp>query[MAXN];
void update(int a,int b,int c,int be,int en,int v){
    if(lazy[c]!=0){
        maxs[c]+=lazy[c];
        mins[c]+=lazy[c];
        if(a!=b){
            lazy[2*c+1]+=lazy[c];
            lazy[2*c+2]+=lazy[c];
        }
        lazy[c]=0;
    }
    if(a>b||a>en||b<be)return;
    if(a>=be&&b<=en){
        maxs[c]+=v;
        mins[c]+=v;
        if(a!=b){
            lazy[2*c+1]+=v;
            lazy[2*c+2]+=v;
        }
        return;
    }
    update(a,(a+b)/2,2*c+1,be,en,v);
    update((a+b)/2+1,b,2*c+2,be,en,v);
    maxs[c]=max(maxs[2*c+1],maxs[2*c+2]);
    mins[c]=min(mins[2*c+1],mins[2*c+2]);
}
ll maxq(int a,int b,int c,int be,int en){
    if(lazy[c]!=0){
        maxs[c]+=lazy[c];
        mins[c]+=lazy[c];
        if(a!=b){
            lazy[2*c+1]+=lazy[c];
            lazy[2*c+2]+=lazy[c];
        }
        lazy[c]=0;
    }
    if(a>b||a>en||b<be)return LLONG_MIN;
    if(a>=be&&b<=en)return maxs[c];
    return max(maxq(a,(a+b)/2,2*c+1,be,en),maxq((a+b)/2+1,b,2*c+2,be,en));
}
ll minq(int a,int b,int c,int be,int en){
    if(lazy[c]!=0){
        maxs[c]+=lazy[c];
        mins[c]+=lazy[c];
        if(a!=b){
            lazy[2*c+1]+=lazy[c];
            lazy[2*c+2]+=lazy[c];
        }
        lazy[c]=0;
    }
    if(a>b||a>en||b<be)return LLONG_MAX;
    if(a>=be&&b<=en)return mins[c];
    return min(minq(a,(a+b)/2,2*c+1,be,en),minq((a+b)/2+1,b,2*c+2,be,en));
}
ll range(int p){
    return maxq(0,q-1,0,p,q-1)-minq(0,q-1,0,p,q-1);
}
ll edge(int s){
    ll mx=maxq(0,q-1,0,0,q-1);
    if(mx>s)return mx-s;
    ll mn=minq(0,q-1,0,0,q-1);
    if(mn<0)return mn;
    else return 0;
}
ll norm(int p,int s){
    ll mx=maxq(0,q-1,0,p,q-1);
    ll mn=minq(0,q-1,0,p,q-1);
    if(maxq(0,q-1,0,p-1,q-1)>mx)return mn;
    else if(minq(0,q-1,0,p-1,q-1)<mn)return mx-s;
}
int calc(int s){
    int lef=0;
    int rig=q-1;
    int mid=(lef+rig)/2;
    while(rig-lef>1){
        if(range(mid)>s)lef=mid;
        else rig=mid;
        mid=(lef+rig)/2;
    }
    if(range(lef)<=s)mid=lef;
    else mid=rig;
    ll lb=0;
    if(mid==0)lb=edge(s);
    else lb=norm(mid,s);
    return sum-lb;
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
    vector<int>ret;
    n=c.size();
    q=v.size();
    for(int i=0;i<q;i++){
        query[l[i]].push_back({i,v[i]});
        if(r[i]!=n-1)query[r[i]+1].push_back({i,-v[i]});
    }
    sum=0;
    memset(maxs,0,sizeof(maxs));
    memset(mins,0,sizeof(mins));
    memset(lazy,0,sizeof(lazy));
    for(int i=0;i<n;i++){
        for(pp j:query[i]){
            sum+=j.second;
            update(0,q-1,0,j.first,q-1,j.second);
        }
        ret.push_back(calc(c[i]));
    }
    return ret;
}

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

candies.cpp: In function 'll norm(int, int)':
candies.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
   79 | }
      | ^

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