QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137070#1140. Distributing Candiesbashkort#0 1ms3812kbC++207.4kb2023-08-09 19:05:182024-07-04 01:28:01

Judging History

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

  • [2024-07-04 01:28:01]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：3812kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 19:05:18]
  • 提交

answer

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

using namespace std;
using ll = long long;

constexpr ll infLL = 3e18;

struct Info {
    pair<ll, int> mx{-infLL, 0}, mn{infLL, 0};
    ll mxans = -infLL, mnans = infLL;
    Info() = default;
    Info(int i, ll x) : mx(x, i), mn(x, i) {}
};

Info operator+(const Info &l, const Info &r) {
    Info res{};
    res.mx = max(l.mx, r.mx);
    res.mn = min(l.mn, r.mn);
    res.mxans = max({l.mxans, r.mxans, r.mx.first - l.mn.first});
    res.mnans = min({l.mnans, r.mnans, r.mn.first - l.mx.first});
    return res;
}

namespace SegmentTree {
    vector<Info> t;
    vector<ll> tag;
    int sz = 1;

    void apply(int x, ll tg) {
        tag[x] += tg;
        t[x].mx.first += tg, t[x].mn.first += tg;
    }

    void push(int x) {
        if (tag[x]) {
            apply(x << 1, tag[x]);
            apply(x << 1 | 1, tag[x]);
            tag[x] = 0;
        }
    }

    void pull(int x) {
        t[x] = t[x << 1] + t[x << 1 | 1];
    }

    void init(int n) {
        sz = 1 << __lg(n) + !!(n & (n - 1));
        t.resize(sz << 1), tag.assign(sz << 1, 0);
        for (int i = 0; i < n; ++i) {
            t[i + sz] = Info(i, 0);
        }
        for (int i = sz - 1; i > 0; --i) {
            pull(i);
        }
    }

    void rangeAdd(int l, int r, int tg, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            return apply(x, tg);
        }
        int mid = lx + rx >> 1;
        push(x);
        rangeAdd(l, r, tg, x << 1, lx, mid);
        rangeAdd(l, r, tg, x << 1 | 1, mid, rx);
        pull(x);
    }

    ll query(int i, int x = 1, int lx = 0, int rx = sz) {
        while (lx + 1 < rx) {
            push(x);
            int mid = lx + rx >> 1;
            if (i < mid) {
                rx = mid;
                x = x << 1;
            } else {
                lx = mid;
                x = x << 1 | 1;
            }
        }
        return t[x].mx.first;
    }

    pair<ll, int> findMin(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return {infLL, -1};
        }
        if (l <= lx && rx <= r) {
            return t[x].mn;
        }
        int mid = lx + rx >> 1;
        push(x);
        return min(findMin(l, r, x << 1, lx, mid), findMin(l, r, x << 1 | 1, mid, rx));
    }

    pair<ll, int> findMax(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return {-infLL, -1};
        }
        if (l <= lx && rx <= r) {
            return t[x].mx;
        }
        int mid = lx + rx >> 1;
        push(x);
        return max(findMax(l, r, x << 1, lx, mid), findMax(l, r, x << 1 | 1, mid, rx));
    }

    pair<ll, int> queryMax(ll aim, int x, int lx, int rx) {
        assert(t[x].mx.first >= aim);
        if (lx + 1 == rx) {
            return t[x].mx;
        }
        int mid = lx + rx >> 1;
        push(x);
        if (t[x << 1 | 1].mx.first >= aim) {
            return queryMax(aim, x << 1 | 1, mid, rx);
        } else {
            return queryMax(aim, x << 1, lx, mid);
        }
    }

    pair<ll, int> queryMin(ll aim, int x, int lx, int rx) {
        assert(t[x].mn.first <= aim);
        if (lx + 1 == rx) {
            return t[x].mn;
        }
        int mid = lx + rx >> 1;
        push(x);
        if (t[x << 1 | 1].mn.first <= aim) {
            return queryMin(aim, x << 1 | 1, mid, rx);
        } else {
            return queryMin(aim, x << 1, lx, mid);
        }
    }

    pair<int, int> findSegmentBiggerThanC(int C, int x = 1, int lx = 0, int rx = sz) {
        pair<int, int> s{-1, -1};
        while (lx + 1 < rx && t[x].mxans >= C) {
            int mid = lx + rx >> 1;
            push(x);
            if (t[x << 1 | 1].mx.first - t[x << 1].mn.first >= C) {
                int R = queryMax(C + t[x << 1].mn.first, x << 1 | 1, mid, rx).second;
                s = max(s, {R, t[x << 1].mn.second});
            }
            if (t[x << 1 | 1].mxans >= C) {
                x = x << 1 | 1;
                lx = mid;
            } else {
                x = x << 1;
                rx = mid;
            }
        }
        return s;
    }

    pair<int, int> findSegmentSmallerThanC(int C, int x = 1, int lx = 0, int rx = sz) {
        assert(C <= 0);
        pair<int, int> s{-1, -1};
        while (lx + 1 < rx && t[x].mnans <= C) {
            int mid = lx + rx >> 1;
            push(x);
            if (t[x << 1 | 1].mn.first - t[x << 1].mx.first <= C) {
                int R = queryMin(C + t[x << 1].mx.first, x << 1 | 1, mid, rx).second;
                s = max(s, {R, t[x << 1].mx.second});
            }
            if (t[x << 1 | 1].mnans <= C) {
                x = x << 1 | 1;
                lx = mid;
            } else {
                x = x << 1;
                rx = mid;
            }
        }
        return s;
    }
};

void massert(bool f) {
    while (!f) {
        cout << "why" << endl;
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> L,
                                    std::vector<int> R, std::vector<int> V) {
    int n = c.size(), q = size(L);

    std::vector<int> answers(n);
    vector<vector<int>> updates(n + 1);

    for (int i = 0; i < q; ++i) {
        updates[L[i]].push_back(i);
        updates[R[i] + 1].push_back(~i);
    }

    SegmentTree::init(q + 1);

    ll sumAll = 0;

    for (int i = 0; i < n; ++i) {
        for (int j : updates[i]) {
            if (j >= 0) {
                sumAll += V[j];
                SegmentTree::rangeAdd(j + 1, q + 1, V[j]);
            } else {
                j = ~j;
                sumAll -= V[j];
                SegmentTree::rangeAdd(j + 1, q + 1, -V[j]);
            }
        }
        int rbig = q + 1, lbig = -1;
        for (rbig -= 1; rbig >= 0; --rbig) {
            auto [x, y] = SegmentTree::findMin(0, rbig + 1);
            ll xx = SegmentTree::query(rbig);
            if (xx - x >= c[i]) {
                lbig = y;
                break;
            }
        }
        int rsmall = q + 1, lsmall = -1;
        for (rsmall -= 1; rsmall >= 0; --rsmall) {
            auto [x, y] = SegmentTree::findMax(0, rsmall + 1);
            ll xx = SegmentTree::query(rsmall);
            if (xx - x <= -c[i]) {
                lsmall = y;
                break;
            }
        }
//        auto [rbig, lbig] = SegmentTree::findSegmentBiggerThanC(c[i]);
//        auto [rsmall, lsmall] = SegmentTree::findSegmentSmallerThanC(-c[i]);
        if (rsmall != -1) {
            assert(SegmentTree::query(rsmall) - SegmentTree::query(lsmall) <= -c[i]);
            rsmall = SegmentTree::findMin(lsmall, rsmall + 1).second;
        }
        if (rbig != -1) {
            assert(SegmentTree::query(rbig) - SegmentTree::query(lbig) >= c[i]);
            rbig = SegmentTree::findMax(lbig, rbig + 1).second;
        }
        rsmall = max(rsmall, SegmentTree::findMin(0, q + 1).second);
        if (rsmall <= rbig) {
            ll got = c[i] + sumAll - SegmentTree::query(rbig);
            massert(got >= 0 && got <= c[i]);
            answers[i] = got;
        } else {
            ll got = sumAll - SegmentTree::query(rsmall);
            massert(got >= 0 && got <= c[i]);
            answers[i] = got;
        }
    }

    return answers;
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 3
Accepted
time: 1ms
memory: 3780kb

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
Accepted
time: 1ms
memory: 3780kb

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 17223 0 0 0 0 0 0 0 0

result:

ok 3 lines

Test #3:

score: -3
Time Limit Exceeded

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
10
5895610 429664 3124 17993 758457 101345 5102817 1127952 59 81146
2000
6 7 44356
5 7 77812
1 4 -41353
1 7 -81697
2 5 -26607
4 9 84461
4 7 -44947
1 6 42622
3 5 -99951
0 1 -77687
2 6 52280
5 9 5073
1 9 67601
6 8 -6669
0 6 42368
4 6 22221
1 3 48306
3 6 -23492
...

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
Time Limit Exceeded

Test #9:

score: 27
Accepted
time: 1ms
memory: 3812kb

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:

ok 3 lines

Test #10:

score: -27
Time Limit Exceeded

input:

lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg
2000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1...

output:

Unauthorized output

result:

Subtask #4:

score: 0
Time Limit Exceeded

Test #16:

score: 0
Time Limit Exceeded

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 繁體中文 简体中文

伺服器時間: 2024-11-29 17:28:20 | 開源專案