제출 #491652

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

candies

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 100;
const ll inf = (ll)1e18;

struct Node{
    ll mx;
    ll low;
    ll lzy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    T[node].mx += T[node].lzy;
    T[node].low += T[node].lzy;
    if(cl != cr){
        T[node * 2].lzy += T[node].lzy;
        T[node * 2 + 1].lzy += T[node].lzy;
    }
    T[node].lzy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, ll v){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lzy += v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, v);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
    T[node].mx = max(T[node * 2].mx, T[node * 2 + 1].mx);
    T[node].low = min(T[node * 2].low, T[node * 2 + 1].low);
}

vector<pii> Q[N];


ll getval(int node, int cl, int cr, int tl, int tr, int ff){
    push(node, cl, cr);
    if(cr < tl || cl > tr) {
        if(ff == 0) return inf;
        else return -inf;
    }
    if(cl >= tl && cr <= tr){
        if(ff == 0){
            return T[node].low;
        }
        else{
            return T[node].mx;
        }
    }
    int mid = (cl + cr) / 2;
    ll lef = getval(node * 2, cl, mid, tl, tr, ff);
    ll rig = getval(node * 2 + 1, mid + 1, cr, tl, tr, ff);
    if(ff == 0)
        return min(lef, rig);
    else
        return max(lef, rig);
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v){
    int n = c.size();
    int q = l.size();
    int m = q + 2;
    upd(1, 0, m - 1, 0, m - 1, +inf);
    upd(1, 0, m - 1, 1, m - 1, -inf);
    for(int i = 0 ;i < q; i ++ ){
        Q[l[i]].push_back(mp(i + 2, +v[i]));
        Q[r[i] + 1].push_back(mp(i + 2, -v[i]));
    }
    int iq;
    int nex;
    ll las;
    ll fir, bef;
    vector<int> soln;
    ll xx;
    for(int i = 0 ; i < n; i ++ ){
        for(auto x : Q[i]){
            upd(1, 0, m - 1, x.fi, m - 1, x.se);
        }
        iq = m - 1;
        for(int lg = 18; lg >= 0; lg -- ){
            nex = (iq - (1 << lg));
            if(nex < 0) continue;
            if(getval(1, 0, m - 1, nex, m - 1, 1) - getval(1, 0, m - 1, nex, m - 1, 0) <= c[i]){
                iq = nex;
            }
        }
        las = getval(1, 0, m - 1, m - 1, m - 1, 0);
        fir = getval(1, 0, m - 1, iq, iq, 0);
        bef = getval(1, 0, m - 1, iq - 1, iq - 1, 0);
        if(bef > fir){
            ll wall_low = getval(1, 0, m - 1, iq, m - 1, 0);
            xx = las - wall_low;
        }
        else{
            ll wall_high = getval(1, 0, m - 1, iq, m - 1, 1);
            xx = c[i] - (wall_high - las);
        }
        soln.push_back(xx);
    }
    return soln;
}

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