제출 #1221515

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

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

// total, max prefix, max loc, min prefix, min loc

vector<ll> dummy = {0, (ll)-pow(10, 18), -1, (ll)pow(10, 18), -1};

int q;
vector<vector<ll>> st;
vector<int> v;

void merge(vector<ll>& node, vector<ll> l, vector<ll> r){
    node[0] = l[0]+r[0];
    node[1] = max(l[1], r[1]+l[0]);
    node[2] = l[1] > r[1]+l[0] ? l[2] : r[2];
    node[3] = min(l[3], r[3]+l[0]);
    node[4] = l[3] < r[3]+l[0] ? l[4] : r[4];
}

void update(int pos, int val, int node=1, int tl=0, int tr=q-1){
    if (tl == tr){
        st[node][0] += val;
        st[node][1] = max(0ll, st[node][0]);
        st[node][2] = st[node][0] > 0 ? pos : pos-1;
        st[node][3] = min(0ll, st[node][0]);
        st[node][4] = st[node][0] < 0 ? pos : pos-1;
        return;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) update(pos, val, node*2, tl, tm);
    else update(pos, val, node*2+1, tm+1, tr);
    merge(st[node], st[node*2], st[node*2+1]);
}

vector<ll> query(int l, int r, int node=1, int tl=0, int tr=q-1){
    if (l > r) return dummy;
    if (r < tl || tr < l) return dummy;
    if (l <= tl && tr <= r) return st[node];
    int tm = (tl+tr)/2;
    vector<ll> res = dummy;
    if (l <= tm) res = query(l, r, node*2, tl, tm);
    if (tm+1 <= r) merge(res, res, query(l, r, node*2+1, tm+1, tr));
    return res;
}

int solve(int c){
    int lo=-1, hi=q;
    while (lo < hi-1){
        int mid = (lo+hi)/2;
        vector<ll> res = query(mid, q-1);
        if (res[1]-res[3] >= c) lo = mid;
        else hi = mid;
    }
    if (lo == -1 || v[lo] < 0){
        if (lo == q-1) return 0;
        vector<ll> res = query(lo+1, q-1);
        int loc = query(lo+1, q-1)[4];
        return query(loc+1, q-1)[0];
    }
    else {
        if (lo == q-1) return c;
        int loc = query(lo+1, q-1)[2];
        return c+query(loc+1, q-1)[0];
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    ::v = v;
    int n = c.size();
    q = l.size();
    st.resize(4*q, dummy);
    for (int i=0; i<q; i++) update(i, 0);
    vector<pair<int,int>> ev;
    for (int i=0; i<q; i++){
        ev.push_back({l[i], i});
        ev.push_back({r[i]+1, i});
    }
    sort(ev.begin(), ev.end());
    vector<int> res(n);
    int cur = 0;
    for (int i=0; i<n; i++){
        while (cur < 2*q && ev[cur].first == i){
            if (i == l[ev[cur].second]) update(ev[cur].second, v[ev[cur].second]);
            else update(ev[cur].second, -v[ev[cur].second]);
            cur++;
        }
        res[i] = solve(c[i]);
    }
    return res;
}

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