제출 #849069

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

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll sm;
vector<vector<pair<int, int>>> d(nx);

struct node
{
    ll mx, mn, mxidx, mnidx, lz;
    node(int idx): mx(0), mn(0), mxidx(idx), mnidx(idx), lz(0){}
    node(): lz(0){}
};

struct segtree
{
    node d[4*nx];
    node merge(node &a, node &b)
    {
        node res=node(0);
        res.mx=max(a.mx, b.mx);
        res.mn=min(a.mn, b.mn);
        res.mxidx=a.mx>=b.mx?a.mxidx:b.mxidx;
        res.mnidx=a.mn<=b.mn?a.mnidx:b.mnidx;
        res.lz=0;
        return res;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=node(l));
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
        //cout<<d[i].mxidx<<' '<<d[i].mnidx<<'\n';
    }
    void pushlz(int l, int r, int i)
    {
        d[i].mx+=d[i].lz; d[i].mn+=d[i].lz;
        if (l==r) return void(d[i].lz=0);
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        d[i].lz=0;
    }
    void update(int l, int r, int i, int ql, int v)
    {
        pushlz(l, r, i);
        if (r<ql) return;
        if (ql<=l) return d[i].lz+=v, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, v);
        update(md+1, r, 2*i+1, ql, v);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    node query(int l, int r, int i, ll c, node ans)
    {
        pushlz(l, r, i);
        if (l==r) return merge(d[i], ans);
        int md=(l+r)/2;
        pushlz(l, md, 2*i); pushlz(md+1, r, 2*i+1);
        node tmp=merge(ans, d[2*i+1]);
        if (tmp.mx-tmp.mn>=c) return query(md+1, r, 2*i+1, c, ans);
        return query(l, md, 2*i, c, tmp); 
    }
} s;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n=c.size(), t=l.size();
    d[0].push_back({1, 1e9+5});
    d[0].push_back({2, -1e9-5});
    for (int i=1; i<=t; i++)
    {
        d[l[i-1]].push_back({i+2, v[i-1]});
        d[r[i-1]+1].push_back({i+2, -v[i-1]});
    }
    vector<int> ans(n);
    s.build(1, t+2, 1);
    for (int i=0; i<n; i++)
    {
        for (auto [x, y]:d[i]) sm+=y, s.update(1, t+2, 1, x, y);
        node tmp(-1);
        tmp.mx=LLONG_MIN; tmp.mn=LLONG_MAX;
        node res=s.query(1, t+2, 1, c[i], tmp);
        //cout<<t+2<<' '<<i<<' '<<c[i]<<' '<<res.mx<<' '<<res.mn<<' '<<res.mxidx<<' '<<res.mnidx<<'\n';
        if (res.mnidx<=res.mxidx) ans[i]=max(0ll, c[i]-(res.mx-sm));
        else ans[i]=max(0ll, sm-res.mn);
    }
    return ans;
}

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