제출 #837181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837181		QwertyPi	Distributing Candies (IOI21_candies)	C++17	8 / 100	274 ms	37944 KiB

candies

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

using namespace std;

const int N_MAX = 2e5 + 11;
int n, q;

struct node{
    int pref_max, pref_min, sum;
    node() : pref_max(0), pref_min(0), sum(0){}
    node(int v) : pref_max(max(0LL, v)), pref_min(min(0LL, v)), sum(v){};
};

struct update{
    int t, pos, val;
};

node operator+ (const node& a, const node& b){
    node res;
    res.pref_max = max(a.pref_max, a.sum + b.pref_max);
    res.pref_min = min(a.pref_min, a.sum + b.pref_min);
    res.sum = a.sum + b.sum;
    return res;
}

node t[N_MAX << 2];
int a[N_MAX];

void st_update(int qi, int qv, int v = 0, int l = 0, int r = q - 1){
    if(l == r) t[v] = node(qv), a[qi] = qv;
    else {
        int m = (l + r) / 2;
        if(qi <= m) st_update(qi, qv, v * 2 + 1, l, m);
        else st_update(qi, qv, v * 2 + 2, m + 1, r);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }
}

node st_suffix(int qi, int v = 0, int l = 0, int r = q - 1){
    if(qi > r) return 0;
    if(l == r) return t[v];
    else {
        int m = (l + r) / 2;
        if(qi <= m) return st_suffix(qi, v * 2 + 1, l, m) + t[v * 2 + 2];
        else return st_suffix(qi, v * 2 + 2, m + 1, r);
    }
}

int st_position(int c, node s = 0, int v = 0, int l = 0, int r = q - 1){
    if(l == r) return l;
    else {
        int m = (l + r) / 2;
        node s2 = t[v * 2 + 2] + s;
        if(s2.pref_max - s2.pref_min < c) return st_position(c, s2, v * 2 + 1, l, m);
        else return st_position(c, s, v * 2 + 2, m + 1, r);
    }
}

int f(node v, int x, int c){
    if(v.pref_max - v.pref_min < c){
        if(x > c - v.pref_max) x = c - v.pref_max;
        if(x < -v.pref_min) x = v.pref_min;
        return x + v.sum;
    }else{
        x += v.sum;
        if(x < 0) x = 0;
        if(x > c) x = c;
        return x;
    }
}

vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
    n = c.size(), q = l.size();
    vector<update> Q;
    for(int i = 0; i < q; i++){
        Q.push_back({l[i], i, v[i]});
        Q.push_back({r[i] + 1, i, 0});
    }
    sort(Q.begin(), Q.end(), [](update a, update b){
        return a.t < b.t;
    });
    int qid = 0;
    vector<int32_t> s(n);
    for(int i = 0; i < n; i++){
        while(qid < (int) Q.size() && Q[qid].t <= i) st_update(Q[qid].pos, Q[qid].val), qid++;
        int pos = st_position(c[i]);
        s[i] = f(node(a[pos++]), s[i], c[i]);
        s[i] = f(st_suffix(pos), s[i], c[i]);
    }
    return s;
}

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