QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521152#1140. Distributing Candiesarbuzick#0 0ms0kbC++206.8kb2024-08-15 22:18:342024-08-15 22:18:35

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 22:18:35]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-08-15 22:18:34]
  • 提交

answer

#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

struct Node {
    long long mn, mn2, mx, mx2, mn_assign, mx_assign, add;

    Node() {
        mn = mn2 = mx = mx2 = 0;
        mn_assign = inf;
        mx_assign = 0;
        add = 0;
    }
};

constexpr int R = 1 << 18;

Node tree[R * 2];

void build() {
    for (int i = 0; i < R; ++i) {
        tree[i + R].mn2 = inf;
        tree[i + R].mx2 = -inf;
    }
}

void push(int node) {
    if (tree[node].add != 0) {
        tree[node * 2].mn += tree[node].add;
        tree[node * 2].mn2 += tree[node].add;
        tree[node * 2].mx += tree[node].add;
        tree[node * 2].mx2 += tree[node].add;
        tree[node * 2].mn_assign += tree[node].add;
        tree[node * 2].mx_assign += tree[node].add;
        tree[node * 2].add += tree[node].add;

        tree[node * 2 + 1].mn += tree[node].add;
        tree[node * 2 + 1].mn2 += tree[node].add;
        tree[node * 2 + 1].mx += tree[node].add;
        tree[node * 2 + 1].mx2 += tree[node].add;
        tree[node * 2 + 1].mn_assign += tree[node].add;
        tree[node * 2 + 1].mx_assign += tree[node].add;
        tree[node * 2 + 1].add += tree[node].add;
    }
    tree[node].add = 0;
    if (tree[node].mn_assign < inf) {
        if (tree[node * 2].mx > tree[node].mn_assign) {
            tree[node * 2].mx = tree[node].mn_assign;
        }
        tree[node * 2].mn_assign = min(tree[node * 2].mn_assign, tree[node].mn_assign);
        if (tree[node * 2 + 1].mx > tree[node].mn_assign) {
            tree[node * 2 + 1].mx = tree[node].mn_assign;
        }
        tree[node * 2 + 1].mn_assign = min(tree[node * 2 + 1].mn_assign, tree[node].mn_assign);
    }
    tree[node].mn_assign = inf;
    if (tree[node].mx_assign >= 0) {
        if (tree[node * 2].mn < tree[node].mx_assign) {
            tree[node * 2].mn = tree[node].mx_assign;
        }
        tree[node * 2].mx_assign = max(tree[node * 2].mx_assign, tree[node].mx_assign);
        if (tree[node * 2 + 1].mn < tree[node].mx_assign) {
            tree[node * 2 + 1].mn = tree[node].mx_assign;
        }
        tree[node * 2 + 1].mx_assign = max(tree[node * 2 + 1].mx_assign, tree[node].mx_assign);
    }
    tree[node].mx_assign = 0;
}

void add_val(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        tree[node].mn += val;
        tree[node].mn2 += val;
        tree[node].mx += val;
        tree[node].mx2 += val;
        tree[node].mn_assign += val;
        tree[node].mx_assign += val;
        tree[node].add += val;
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    add_val(ql, qr, val, node * 2, nl, nm);
    add_val(ql, qr, val, node * 2 + 1, nm, nr);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
    vector<long long> vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mn2, tree[node * 2 + 1].mn2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mn2 = vals[1];
    tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
    vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mx2, tree[node * 2 + 1].mx2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mx2 = vals.rbegin()[1];
}

void fix_mn(long long mn, int node = 1, int nl = 0, int nr = R) {
    if (mn <= tree[node].mn) {
        return;
    }
    if (nl == nr - 1) {
        tree[node].mn = tree[node].mx = mn;
        return;
    }
    if (mn <= tree[node].mn2) {
        tree[node].mn = mn;
        tree[node].mx_assign = mn;
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    fix_mn(mn, node * 2, nl, nm);
    fix_mn(mn, node * 2 + 1, nm, nr);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
    vector<long long> vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mn2, tree[node * 2 + 1].mn2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mn2 = vals[1];
    tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
    vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mx2, tree[node * 2 + 1].mx2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mx2 = vals.rbegin()[1];
}

void fix_mx(long long mx, int node = 1, int nl = 0, int nr = R) {
    if (tree[node].mx <= mx) {
        return;
    }
    if (nl == nr - 1) {
        tree[node].mn = tree[node].mx = mx;
        return;
    }
    if (mx >= tree[node].mx2) {
        tree[node].mx = mx;
        tree[node].mn_assign = mx;
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    fix_mx(mx, node * 2, nl, nm);
    fix_mx(mx, node * 2 + 1, nm, nr);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
    vector<long long> vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mn2, tree[node * 2 + 1].mn2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mn2 = vals[1];
    tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
    vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mx2, tree[node * 2 + 1].mx2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mx2 = vals.rbegin()[1];
}

long long get(int pos, int node = 1, int nl = 0, int nr = R) {
    if (nl == pos && nr == pos + 1) {
        return tree[node].mn;
    }
    if (nr <= pos && pos < nl) {
        return 0;
    }
    push(node);
    int nm = (nl + nr) / 2;
    long long ans = get(pos, node * 2, nl, nm) + get(pos, node * 2 + 1, nm, nr);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
    vector<long long> vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mn2, tree[node * 2 + 1].mn2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mn2 = vals[1];
    tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
    vals = {tree[node * 2].mn, tree[node * 2 + 1].mn, tree[node * 2].mx2, tree[node * 2 + 1].mx2, tree[node * 2].mx, tree[node * 2 + 1].mx};
    sort(vals.begin(), vals.end());
    tree[node].mx2 = vals.rbegin()[1];
    return ans;
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
    int n = c.size();
    int q = v.size();
    vector<int> ans(n);
    for (int i = 0; i < q; ++i) {
        r[i]++;
        add_val(l[i], r[i], v[i]);
        fix_mn(0);
        fix_mx(c[0]);
    }
    for (int i = 0; i < n; ++i) {
        ans[i] = get(i);
    }
    return ans;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
8
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
8
0 7 1
0 7 1
0 7 300000000
0 7 994967293
0 7 1
0 7 1000000000
0 7 1000000000
0 7 1000000000

output:

Unauthorized output

result:

Subtask #2:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
200000
11408901 370732653 37843 28 53693 15782410 103 297546 1112427 170319071 26 1 6172 11614171 431 884673599 1 3 50085 154 57 28200 145886 898969 74758 72 845768 6 69787 11 31012465 55362 253 2363145 47186217 1103 19622 594 7867 1 4299 28130 48 4689582 12 ...

output:

Unauthorized output

result:

Subtask #3:

score: 0
Runtime Error

Test #9:

score: 0
Runtime Error

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000...

output:

Unauthorized output

result:

Subtask #4:

score: 0
Runtime Error

Test #16:

score: 0
Runtime Error

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
10
11 440 51 41 11 1 3 108 148 14
10
0 9 60
0 9 -9
0 9 -30
0 9 41
0 9 82
0 9 69
0 9 -79
0 9 -39
0 9 72
0 9 41

output:

Unauthorized output

result:

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-11-29 12:41:12 | OpenSource Project