제출 #989451

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

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
#define ll long long
ll sum[4*maxn],mx[4*maxn],mn[4*maxn];

void update(int l,int r,int id,int p,int val){
    if(l==r){
        if(sum[id]) sum[id]=0;
        else sum[id]=val;
        mx[id]=max(0LL,sum[id]);
        mn[id]=min(0LL,sum[id]);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(l,mid,id<<1,p,val);
    else update(mid+1,r,id<<1|1,p,val);
    sum[id]=sum[id<<1]+sum[id<<1|1];
    mx[id]=max(mx[id<<1],sum[id<<1]+mx[id<<1|1]);
    mn[id]=min(mn[id<<1],sum[id<<1]+mn[id<<1|1]);
}
int query(int l,int r,int id,int c){
    if(l==r) return min(max(sum[id],0LL),(ll)c);
    int mid=(l+r)>>1;
    if(mx[id<<1|1]-mn[id<<1|1]>c) return query(mid+1,r,id<<1|1,c);
    int cc=query(l,mid,id<<1,c);
    if(cc+mx[id<<1|1]>c) return c+sum[id<<1|1]-mx[id<<1|1];
    if(cc+mn[id<<1|1]<0) return sum[id<<1|1]-mn[id<<1|1];
    return cc+sum[id<<1|1];
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n=(int)c.size(),q=(int)l.size();
    vector<int> a(n);
    vector<vector<int>> g(n+1);
    for(int i=0;i<q;i++) g[l[i]].push_back(i+1),g[r[i]+1].push_back(-i-1);
    for(int i=0;i<n;i++){
        for(int id:g[i]){
            int p=abs(id)-1;
            update(0,q-1,1,p,v[p]);
        }
        a[i]=query(0,q-1,1,c[i]);
    }
    return a;
}

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