제출 #535586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535586		mario05092929	사탕 분배 (IOI21_candies)	C++17	8 / 100	1323 ms	33664 KiB

candies

#include "candies.h"
#define x first
#define y second
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vec;
typedef pair <int,int> pi;
typedef long long ll;
int a[200005],ql[200005],qr[200005],qv[200005];
int n,Q;
ll sum[800025],mx[800025],mn[800025];
vec q[200005];

void update(int x,int l,int r,int wi,int val) {
    if(wi < l||r < wi) return;
    if(l == r) {
        sum[x] = mx[x] = mn[x] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(x*2,l,mid,wi,val), update(x*2+1,mid+1,r,wi,val);
    sum[x] = sum[x*2]+sum[x*2+1];
    mx[x] = max(mx[x*2],sum[x*2]+mx[x*2+1]);
    mn[x] = min(mn[x*2],sum[x*2]+mn[x*2+1]);
}

ll querySum(int x,int l,int r,int rl,int rr) {
    if(rl > r||l > rr) return 0;
    if(rl <= l&&r <= rr) return sum[x];
    int mid = (l + r) >> 1;
    return querySum(x*2,l,mid,rl,rr)+querySum(x*2+1,mid+1,r,rl,rr);
}

ll queryMx(int x,int l,int r,int rl,int rr,ll cnt) {
    if(rl > r||l > rr) return 0;
    if(rl <= l&&r <= rr) return mx[x]+cnt;
    int mid = (l + r) >> 1;
    return max(queryMx(x*2,l,mid,rl,rr,cnt),queryMx(x*2+1,mid+1,r,rl,rr,cnt+sum[x*2]));
}

ll queryMn(int x,int l,int r,int rl,int rr,ll cnt) {
    if(rl > r||l > rr) return 1e18;
    if(rl <= l&&r <= rr) return mn[x]+cnt;
    int mid = (l + r) >> 1;
    return min(queryMn(x*2,l,mid,rl,rr,cnt),queryMn(x*2+1,mid+1,r,rl,rr,cnt+sum[x*2]));
}

vec distribute_candies(vec C,vec L,vec R,vec V) {
    n = C.size(), Q = L.size();
    for(int i = 0;i < n;i++) {
        a[i+1] = C[i];
    }
    for(int i = 0;i < Q;i++) {
        ql[i+1] = L[i]+1;
        qr[i+1] = R[i]+1;
        qv[i+1] = V[i];
        q[ql[i+1]].pb(i+1);
        q[qr[i+1]+1].pb(-i-1);
    }
    vec ans;
    for(int i = 1;i <= n;i++) {
        for(int j : q[i]) {
            if(j > 0) update(1,0,Q,j,qv[j]);
            else update(1,0,Q,-j,0);
        }
        int l = 0, r = Q;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(queryMx(1,0,Q,mid,Q,0)-queryMn(1,0,Q,mid,Q,0) > a[i]) l = mid+1;
            else r = mid;
        }
        int idx = l;
        if(!idx) ans.pb(querySum(1,0,Q,0,Q)-queryMn(1,0,Q,0,Q,0));
        else {
            ll mn = queryMn(1,0,Q,idx,Q,0);
            ll mx = queryMx(1,0,Q,idx,Q,0);
            ll bef = querySum(1,0,Q,idx-1,idx-1);
            if(bef < mn) ans.pb((ll)a[i]-(mx-querySum(1,0,Q,0,Q)));
            else ans.pb(querySum(1,0,Q,0,Q)-mn);
        }
    }
    return ans;
}

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