제출 #591494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591494		Lucpp	사탕 분배 (IOI21_candies)	C++17	27 / 100	401 ms	26400 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Op{
    ll add = 0, lo = -INF, hi = INF;
};
Op merge(Op a, Op b){
    Op c;
    c.add = a.add+b.add;
    a.lo += b.add;
    a.hi += b.add;
    if(b.lo > a.hi){
        c.lo = c.hi = b.lo;
    }
    else if(b.hi < a.lo){
        c.lo = c.hi = b.hi;
    }
    else{
        c.lo = max(a.lo, b.lo);
        c.hi = min(a.hi, b.hi);
    }
    return c;
}

int cap;
vector<Op> O;
vector<bool> lazy;

void apply(Op o, int i){
    O[i] = merge(O[i], o);
    lazy[i] = true;
}
void push(int i){
    if(lazy[i]){
        apply(O[i], 2*i);
        apply(O[i], 2*i+1);
        O[i] = Op();
        lazy[i] = false;
    }
}
void upd(int l, int r, Op x, int a, int b, int i){
    if(l <= a && b <= r) apply(x, i);
    else if(b < l || r < a) return;
    else{
        push(i);
        int m = (a+b)/2;
        upd(l, r, x, a, m, 2*i);
        upd(l, r, x, m+1, b, 2*i+1);
    }
}
void go(int p, int a, int b, int i){
    if(a == b) return;
    push(i);
    int m = (a+b)/2;
    if(p <= m) go(p, a, m, 2*i);
    else go(p, m+1, b, 2*i+1);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int)c.size();
    int q = (int)l.size();
    for(cap = 1; cap < n; cap *= 2);
    O.resize(2*cap);
    lazy.resize(2*cap);

    for(int i = 0; i < q; i++){
        upd(l[i]+1, r[i]+1, {v[i], 0, c[0]}, 1, cap, 1);
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        go(i+1, 1, cap, 1);
        ans[i] = (int)min(O[i+cap].hi, max(O[i+cap].lo, O[i+cap].add));
    }
    return ans;
}

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