제출 #1326726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326726		BigBadBully	사탕 분배 (IOI21_candies)	C++20	100 / 100	1529 ms	58656 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
const int inf = 1e18;
using namespace std;
struct node{
    int pref = 0,sub= 0,sum= 0,suf=0,mxp =0;
    node operator+(node b)
    {
        node res;
        res.sum = sum+b.sum;
        res.pref = min(pref,b.pref+sum);
        res.suf = min(b.suf,suf+b.sum);
        res.mxp=max(mxp,b.mxp+sum);
        res.sub = min({sub,b.sub,suf+b.pref});
        return res;
    }
};

struct seggy{
    int n;
    vector<node> t;
    seggy(int sz){
        n = sz;
        t.resize(4*n,node());
    }
    void update(int l,int r,int idx,int i,int x)
    {
        if(l>i || r<i)return;
        if(l==r)
        {
            node&a = t[idx];
            a.sum = x;
            a.pref=min(x,0ll);
            a.suf = a.pref;
            a.sub = min(0ll,x);
            a.mxp = max(0ll,x);
            return;
        }
        int mid = l+r>>1;
        update(l,mid,2*idx,i,x);
        update(mid+1,r,2*idx+1,i,x);
        t[idx] = t[2*idx]+t[2*idx+1];
    }
    void update(int i,int x)
    {
        update(0,n-1,1,i,x);
    }
    node query(int l,int r,int L,int R,int idx)
    {
        if(l>R||r<L)
            return node();
        if(l>=L&&r<=R)
            return t[idx];
        int mid = l+r>>1;
        return query(l,mid,L,R,2*idx)+query(mid+1,r,L,R,2*idx+1);
    }
    node query(int l,int r)
    {
        if(l>r)
            return node();
        return query(0,n-1,l,r,1);
    }
};
vector<signed> distribute_candies(vector<signed> c, vector<signed> l,
vector<signed> r, vector<signed> v) {
    int n = c.size();
    int q= l.size();
    vector<vector<pii>> add(n),rem(n);                     
    for(int i = 0;i  <q;i++)
    {
        add[l[i]].push_back({i,v[i]});
        rem[r[i]].push_back({i,v[i]});
    }
    seggy mile(q);
    vector<signed> ans(n);
    for(int i = 0; i< q; i++)mile.update(i,0);
    for(int i = 0; i < n; i++)
    {
        for(pii x:add[i])
            mile.update(x.ff,x.ss);
        int idx = -1;
        if(-mile.query(0,q-1).sub>c[i])
        {
            int l = 0,r = q-1;
            while(r-l)
            {
                int mid = (l+r+1)>>1;
                if(-mile.query(mid,q-1).sub > c[i])
                    l = mid;
                else
                    r = mid-1;
            }
            idx = l;
            l = idx,r = q-1;
            while(r-l)
            {
                int mid = l+r>>1;
                if(-mile.query(idx,mid).sub > c[i])
                    r = mid;
                else
                    l = mid+1;
            }
            idx = l;
        }
        node g = mile.query(idx+1,q-1);
        int lit = -min(0ll,g.pref);
        int big = max(0ll,g.mxp+lit-c[i]);
        ans[i] = g.sum-big+lit;
        for(pii x:rem[i])
            mile.update(x.ff,0);
    }

    
    return ans;
}
vector<signed> brute(vector<signed> c, vector<signed> l,
vector<signed> r, vector<signed> v) {
    int n = c.size();
    int q= l.size();
    vector<signed> ans(n);
    for(int i = 0; i < q; i++)
        for(int j = l[i];j <= r[i];j++)
            ans[j] = max(0ll,min<int>(c[j],ans[j]+v[i]));
      
    return ans;
}
#undef int 

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