QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521155#1140. Distributing Candiesarbuzick#0 6ms32784kbC++206.8kb2024-08-15 22:22:282024-08-15 22:22:28

Judging History

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

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

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
Wrong Answer

Test #1:

score: 3
Accepted
time: 0ms
memory: 32784kb

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:

4lpv73iykswp9e3nppi3jw2qggm5dfz29yy9nzpq
OK
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

result:

ok 3 lines

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 32416kb

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
10
283 43634 101056 10340 6009 5133 30 2 3677888 210
10
1 8 26416
2 7 -51219
2 4 17793
3 7 75426
3 7 22307
1 1 60258
3 7 -29824
0 8 24839
2 8 -60304
0 1 -26411

output:

4lpv73iykswp9e3nppi3jw2qggm5dfz29yy9nzpq
OK
0 0 0 0 0 0 0 0 0 0

result:

wrong answer 3rd lines differ - expected: '0 17223 0 0 0 0 0 0 0 0', found: '0 0 0 0 0 0 0 0 0 0'

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
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 6ms
memory: 32580kb

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:

4lpv73iykswp9e3nppi3jw2qggm5dfz29yy9nzpq
OK
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer 3rd lines differ - expected: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 0ms
memory: 32488kb

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:

4lpv73iykswp9e3nppi3jw2qggm5dfz29yy9nzpq
OK
113 113 113 113 113 113 113 113 113 113

result:

wrong answer 3rd lines differ - expected: '11 208 51 41 11 1 3 108 143 14', found: '113 113 113 113 113 113 113 113 113 113'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-11-29 12:42:40 | OpenSource Project