QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138122#1140. Distributing Candiessomethingnew0 1ms3792kbC++208.7kb2023-08-11 00:06:092023-08-11 00:07:03

Judging History

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

  • [2023-08-11 00:07:03]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：3792kb
查看
  • [2023-08-11 00:06:09]
  • 提交

answer

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
#include "candies.h"
struct segbeb1 {
    vector<array<int, 3>> ar;
    segbeb1(int n, int tpp = 0) {
        ar.clear();
        ar.push_back({n, 0, tpp});
    }
    vector<array<int, 3>> compress(vector<array<int, 3>> art) {
        vector<array<int, 3>> ar2;
        for (auto i : art) {
            if (!ar2.empty() and ar2.back()[2] == 1 and ar2.back()[1] + ar2.back()[0] == i[1] and i[2] == 1) {
                ar2.back()[0] += i[0];
            } else  if (!ar2.empty() and ar2.back()[2] == 0 and ar2.back()[1] == i[1] and i[2] == 0) {
                ar2.back()[0] += i[0];
            } else {
                ar2.push_back(i);
            }
        }
        return ar2;
    }
    void addx(int x) {
        vector<array<int, 3>> ar2;
        int lv = 0;
        for (auto &[cnt, lfvl, add] : ar) {
            lfvl += x;
            if (x > 0) {
                if (lv < lfvl) {
                    if (add == 1) {
                        lfvl = lv;
                        ar2.push_back({cnt, lfvl, add});
                    } else {
                        array<int, 3> lf, rg;
                        lf = {min(cnt, lfvl - lv), lv, 1};
                        ar2.push_back(lf);
                        if (cnt > lf[0]) {
                            rg = {cnt - lf[0], lfvl, 0};
                            ar2.push_back(rg);
                        }
                    }
                } else {
                    ar2.push_back({cnt, lfvl, add});
                }
            } else {
                if (lfvl < 0) {
                    if (add == 0) {
                        lfvl = 0;
                        ar2.push_back({cnt, lfvl, add});
                    } else {
                        array<int, 3> lf, rg;
                        lf = {min(cnt, -lfvl), 0, 0};
                        ar2.push_back(lf);
                        if (cnt > lf[0]) {
                            rg = {cnt - lf[0], 0, 1};
                            ar2.push_back(rg);
                        }
                    }
                } else {
                    ar2.push_back({cnt, lfvl, add});
                }
            }
            lv += cnt;
        }
        ar = compress(ar2);
        //for (auto i : ar)
        //    cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
        //cout << endl;
    }
    int getv(int v) {
        int l = 0;
        for (auto i : ar) {
            if (l + i[0] > v) {
                return i[1] + (v - l) * i[2];
            }
            l += i[0];
        }
        exit(1);
    }
};
struct segbeb2 {
    vector<array<int, 3>> ar;
    int N;
    segbeb2() {
    }
    segbeb2(int n) {
        N = n;
        ar.clear();
        ar.push_back({n + 1, 0, 1});
    }
    vector<array<int, 3>> compress(vector<array<int, 3>> art) {
        vector<array<int, 3>> ar2;
        for (auto i : art) {
            if (!ar2.empty() and ar2.back()[2] == 1 and ar2.back()[1] + ar2.back()[0] == i[1] and i[2] == 1) {
                ar2.back()[0] += i[0];
            } else  if (!ar2.empty() and ar2.back()[2] == 0 and ar2.back()[1] == i[1] and i[2] == 0) {
                ar2.back()[0] += i[0];
            } else {
                ar2.push_back(i);
            }
        }
        return ar2;
    }
    void addx(int x) {
        vector<array<int, 3>> ar2;
        int lv = 0;
        for (auto &[cnt, lfvl, add] : ar) {
            lfvl += x;
            if (x > 0) {
                if (lfvl + cnt * add > N) {
                    if (add == 0) {
                        lfvl = N;
                        ar2.push_back({cnt, lfvl, add});
                    } else {
                        array<int, 3> lf, rg;
                        rg = {min(cnt, lfvl+cnt-N), N, 0};
                        if (cnt > rg[0]) {
                            lf = {cnt - rg[0], N - (cnt-rg[0]), 1};
                            ar2.push_back(lf);
                        }
                        ar2.push_back(rg);
                    }
                } else {
                    ar2.push_back({cnt, lfvl, add});
                }
            } else {
                if (lfvl < 0) {
                    if (add == 0) {
                        lfvl = 0;
                        ar2.push_back({cnt, lfvl, add});
                    } else {
                        array<int, 3> lf, rg;
                        lf = {min(cnt, -lfvl), 0, 0};
                        ar2.push_back(lf);
                        if (cnt > lf[0]) {
                            rg = {cnt - lf[0], 0, 1};
                            ar2.push_back(rg);
                        }
                    }
                } else {
                    ar2.push_back({cnt, lfvl, add});
                }
            }
            lv += cnt;
        }
        ar = compress(ar2);
        //for (auto i : ar)
        //    cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
        //cout << endl;
    }
    int getv(int v) {
        int l = 0;
        for (auto i : ar) {
            if (l + i[0] > v) {
                return i[1] + (v - l) * i[2];
            }
            l += i[0];
        }
        while (1);
    }
};
vector<int> solveallon(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    segbeb1 beba(1e9 + 5);
    for (auto i : v) {
        beba.addx(i);
    }
    vector<int> res(c.size());
    for (int i = 0; i < c.size(); ++i) {
        res[i] = beba.getv(c[i]);
    }
    return res;
}
struct sqrtpart {
    segbeb2 beba;
    bool pus = 1;
    int CC;
    vector<int> vals;
    sqrtpart(int n, int c) {
        beba = segbeb2(c);
        vals.assign(n, {});
        CC = c;
    };
    void trypush() {
        if (pus)
            return;
        pus = 1;
        for (auto &i : vals) {
            i = beba.getv(i);
        }
        beba = segbeb2(CC);
    }
    void givelr(int l, int r, int x) {
        trypush();
        for (int i = l; i < r; ++i) {
            vals[i] += x;
            vals[i] = min(vals[i], CC);
            vals[i] = max(vals[i], 0);
        }
    }
    void giveall(int x) {
        beba.addx(x);
        pus = 0;
    }
    vector<int> getel() {
        trypush();
        return vals;
    }
};
int K = 500;
int nxt(int v) {
    return (v+499)/K*K;
}
vector<int> ceq(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<sqrtpart> a((n+499) / K, {K, c[0]});
    for (int i = 0; i < v.size(); ++i) {
        int lv = l[i], rg = r[i] + 1;
        if (lv % K != 0 and nxt(lv) <= rg) {
            a[lv / K].givelr(lv % K, 500, v[i]);
            lv = nxt(lv);
        }
        while (lv + K <= rg) {
            a[lv / K].giveall(v[i]);
            lv += K;
        }
        a[lv / K].givelr(lv % K, rg % K, v[i]);
    }
    vector<int> res;
    for (auto &i : a) {
        for (auto j : i.getel())
            res.push_back(j);
    }
    while (res.size() > n)
        res.pop_back();
    return res;
    /**/
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<sqrtpart> a((n+499) / K, {K, c[0]});
    for (int i = 0; i < v.size(); ++i) {
        int lv = l[i], rg = r[i] + 1;
        if (lv % K != 0 and nxt(lv) <= rg) {
            a[lv / K].givelr(lv % K, 500, v[i]);
            lv = nxt(lv);
        }
        while (lv + K <= rg) {
            a[lv / K].giveall(v[i]);
            lv += K;
        }
        a[lv / K].givelr(lv % K, rg % K, v[i]);
    }
    vector<int> res;
    for (auto &i : a) {
        for (auto j : i.getel())
            res.push_back(j);
    }
    while (res.size() > n)
        res.pop_back();
    return res;
    /**/
}
#ifdef __APPLE__

int main() {
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        assert(scanf("%d", &c[i]) == 1);
    }

    int q;
    assert(1 == scanf("%d", &q));
    std::vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
    }

    std::vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < (int)ans.size(); ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}
#endif
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: -3
Wrong Answer
time: 1ms
memory: 3728kb

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
Runtime Error

Test #6:

score: 0
Runtime Error

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

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
Runtime Error

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

Test #16:

score: 0
Wrong Answer
time: 1ms
memory: 3728kb

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
11 11 11 11 11 11 11 11 11 11

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2024-11-29 16:34:42 | 開源專案