QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#455944	#1877. Matryoshka Dolls	makrav	WA	300ms	300848kb	C++20	4.7kb	2024-06-27 03:53:55	2024-06-27 03:53:55

Judging History

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

[2024-06-27 03:53:55]
评测

测评结果：WA
用时：300ms
内存：300848kb

查看

[2024-06-27 03:53:55]
提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int K = 550;
const int N = 100010;

int ans_block[(N + K) / K][K][K];
int SPMIN[(N + K) / K][10][K], SPMAX[(100010 + K) / K][10][K];
int nxt[(N + K) / K][100010];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> pos(n + 1);
    for (int i = 0; i < n; i++) {
        pos[a[i]] = i;
    }
    vector<int> bl(n, -1);
    int ind= -1;
    for (int i = 0; i < n; i += K) {
        ind++;
        vector<int> ppos;
        for (int j = i + 1; j <= min(n, i + K); j++) {
            bl[pos[j]] = ind;
            ppos.push_back(pos[j]);
        }
        nxt[ind][n] = n + 1;
        int INDD = ppos.size() - 1;
        for (int j = n - 1; j >= 0; j--) {
            nxt[ind][j] = nxt[ind][j + 1];
            if (bl[j] == ind) nxt[ind][j] = INDD--;
        }
        for (int I = 0; I < ppos.size(); I++) {
            SPMIN[ind][0][I] = a[ppos[I]];
            SPMAX[ind][0][I] = a[ppos[I]];
        }
        for (int j = 1; j < 10; j++) {
            for (int I = 0; I + (1 << j) - 1 < ppos.size(); I++) {
                SPMIN[ind][j][I] = min(SPMIN[ind][j - 1][I], SPMIN[ind][j - 1][I + (1 << (j - 1))]);
                SPMAX[ind][j][I] = max(SPMAX[ind][j - 1][I], SPMAX[ind][j - 1][I + (1 << (j - 1))]);
            }
        }
        sort(ppos.begin(), ppos.end());
        vector<vector<int>> bd_right(ppos.size(), vector<int>(ppos.size())), bd_left(ppos.size(), vector<int>(ppos.size()));
        for (int I = 0; I < ppos.size() - 1; I++) {
            bd_right[I][I] = 1e9;
            bd_left[I][I] = 1e9;
            for (int j = I + 1; j < ppos.size(); j++) {
                bd_right[I][j] = bd_right[I][j - 1];
                bd_left[I][j] = bd_left[I][j - 1];
                if (a[ppos[j]] > a[ppos[I]] && bd_right[I][j] > a[ppos[j]] - a[ppos[I]]) {
                    bd_right[I][j] = a[ppos[j]] - a[ppos[I]];
                }
                if (a[ppos[j]] < a[ppos[I]] && bd_left[I][j] > a[ppos[I]] - a[ppos[j]]) {
                    bd_left[I][j] = a[ppos[I]] - a[ppos[j]];
                }
            }
        }
        vector<vector<int>> ans(ppos.size(), vector<int>(ppos.size()));
        for (int I = ppos.size() - 1; I >= 0; I--) {
            ans[I][I] = 0;
            ans_block[ind][I][I] = ans[I][I];
            for (int j = I - 1; j >= 0; j--) {
                ans[j][I] = ans[j + 1][I];
                int rg = (bd_right[j][I] == 1e9 ? -1 : a[ppos[j]] + bd_right[j][I]);
                int lf = (bd_left[j][I] == 1e9 ? -1 : a[ppos[j]] - bd_left[j][I]);
                if (rg != -1) ans[j][I] += abs(pos[rg] - pos[a[ppos[j]]]);
                if (lf != -1) ans[j][I] += abs(pos[lf] - pos[a[ppos[j]]]);
                if (lf != -1 && rg != -1) ans[j][I] -= abs(pos[lf] - pos[rg]);
                ans_block[ind][j][I] = ans[j][I];
            }
        }
    }
    vector<vector<int>> qrs(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r; l--; r--;
        qrs[i] = {l, r, i};
    }
    sort(qrs.begin(), qrs.end(), [&](vector<int> &x, vector<int> &y) {
        return x[1] < y[1];
    });
    vector<int> Log2(n + 1, 0);
    for (int i = 2; i <= n; i++) Log2[i] = Log2[i / 2] + 1; 
    auto getmax = [&](int block, int l, int r) {
        int lg = Log2[r - l + 1];
        return max(SPMAX[block][lg][l], SPMAX[block][lg][r - (1 << lg) + 1]);
    };
    auto getmin = [&](int block, int l, int r) {
        int lg = Log2[r - l + 1];
        return min(SPMIN[block][lg][l], SPMIN[block][lg][r - (1 << lg) + 1]);
    };
    int IND = 0;

    ind++;
    vector<int> last(ind, -1);
    vector<ll> ANSW(q);
    vector<int> cnt(ind);
    for (int r = 0; r < n; r++) {
        last[bl[r]] = cnt[bl[r]]++;
        while (IND < qrs.size() && qrs[IND][1] == r) {
            int L = qrs[IND][0], R = qrs[IND][1];
            ll ANS = 0;
            for (int j = 0; j < ind; j++) {
                if (nxt[j][L] <= last[j] && last[j] != -1) {
                    ANS += ans_block[j][nxt[j][L]][last[j]];
                }
            }
            int LAST = -1;
            for (int j = 0; j < ind; j++) {
                if (nxt[j][L] <= last[j] && last[j] > -1) {
                    int RG = getmax(j, nxt[j][L], last[j]), LF = getmin(j, nxt[j][L], last[j]);
                    if (LAST != -1) ANS += abs(pos[LF] - pos[LAST]);
                    LAST = RG;
                }
            }
            ANSW[qrs[IND][2]] = ANS;
            IND++;
        }
    }
    for (auto &u : ANSW) cout << u << '\n';
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 9576kb

input:

output:

result:

ok 5 number(s): "7 5 3 1 0"

Test #2:

score: 0

Accepted

time: 1ms

memory: 9852kb

input:

1 1
1
1 1

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 300ms

memory: 300848kb

input:

100000 1
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...

output:

4999950000

result:

ok 1 number(s): "4999950000"

Test #4:

score: 0

Accepted

time: 2ms

memory: 9564kb

input:

20 1
12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7
9 18

output:

result:

ok 1 number(s): "36"

Test #5:

score: 0

Accepted

time: 0ms

memory: 11652kb

input:

20 10
5 16 11 7 19 8 12 13 17 18 6 1 14 3 4 2 15 20 10 9
7 11
7 13
7 17
11 15
1 7
4 6
1 5
6 14
3 5
9 9

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 1ms

memory: 9740kb

input:

20 50
7 3 13 8 9 18 1 15 12 10 20 11 17 16 2 19 5 4 6 14
3 6
5 15
11 20
10 18
9 20
3 17
13 20
16 17
3 20
4 17
15 18
5 19
3 14
8 20
2 20
1 4
15 19
16 20
5 13
14 17
4 10
6 16
8 16
1 12
4 9
11 15
4 20
8 11
3 16
7 7
3 11
3 7
4 4
5 12
6 20
3 14
6 19
6 19
2 14
2 12
5 6
4 6
8 15
10 19
4 14
1 16
1 20
2 13
3...

output:

result:

ok 50 numbers

Test #7:

score: 0

Accepted

time: 1ms

memory: 9732kb

input:

20 100
4 13 20 8 1 18 19 9 17 5 12 7 11 16 6 3 15 10 14 2
4 19
1 6
6 19
4 6
2 17
1 5
11 13
1 15
9 17
9 15
7 20
3 19
10 19
1 10
11 17
10 17
2 18
17 20
12 19
1 3
5 17
7 13
6 18
10 20
1 6
2 17
5 9
4 13
11 13
2 20
7 13
12 17
5 19
17 20
11 19
3 15
3 5
5 11
1 17
10 15
16 20
1 6
2 19
4 12
5 18
9 17
3 6
12 ...

output:

result:

ok 100 numbers

Test #8:

score: 0

Accepted

time: 1ms

memory: 9744kb

input:

20 228
7 3 17 10 16 11 19 5 1 13 20 18 14 2 8 4 6 9 12 15
7 20
2 20
10 13
14 19
1 9
12 20
17 19
9 20
10 12
14 17
4 15
7 16
5 12
13 16
16 18
7 18
1 11
7 17
2 20
6 8
9 17
12 18
7 18
3 4
7 13
1 4
6 12
6 10
3 17
3 4
5 14
7 13
9 20
6 20
2 4
14 17
17 20
1 7
19 20
4 20
14 15
12 16
4 6
4 15
10 11
2 16
2 20
...

output:

result:

ok 228 numbers

Test #9:

score: 0

Accepted

time: 1ms

memory: 9876kb

input:

20 322
3 11 4 1 9 19 7 12 5 17 8 15 10 18 13 2 20 16 14 6
8 14
6 6
3 17
3 16
9 18
7 17
12 13
4 14
12 18
6 13
8 9
3 17
7 20
12 16
10 15
12 16
12 14
16 19
6 7
18 20
6 16
7 14
5 19
12 13
3 14
10 15
11 18
12 20
8 9
1 13
17 18
1 18
4 19
4 9
5 19
4 5
1 2
10 17
11 19
7 14
15 20
20 20
4 7
12 15
7 17
3 13
7 ...

output:

result:

ok 322 numbers

Test #10:

score: 0

Accepted

time: 1ms

memory: 9796kb

input:

20 1000
16 6 17 1 12 11 5 8 10 19 4 18 2 9 14 7 15 3 20 13
1 6
8 9
9 11
5 18
3 20
2 9
17 18
12 12
12 20
5 17
1 8
10 10
2 9
17 19
1 7
7 15
12 19
2 7
9 14
2 14
1 4
15 17
11 19
2 5
3 12
11 14
11 14
13 17
7 8
9 18
2 11
8 11
1 4
4 8
12 13
12 19
7 16
12 16
11 15
5 9
5 18
2 19
11 15
1 15
4 20
4 9
5 14
5 19...

output:

result:

ok 1000 numbers

Test #11:

score: 0

Accepted

time: 0ms

memory: 9680kb

input:

20 1000
16 8 20 2 5 9 14 7 19 3 13 1 6 18 10 4 15 17 12 11
9 19
12 12
12 19
15 15
6 17
9 16
1 10
4 19
10 13
11 18
2 7
12 17
18 19
4 15
3 18
3 17
5 11
14 17
4 16
3 13
10 10
12 20
1 1
4 8
3 11
8 15
6 7
9 12
1 16
12 20
2 9
8 9
8 9
8 20
17 18
15 20
11 20
1 3
8 10
2 6
8 18
4 12
7 12
3 18
5 14
14 15
6 10
...

output:

result:

ok 1000 numbers

Test #12:

score: 0

Accepted

time: 0ms

memory: 9720kb

input:

20 1000
7 16 3 15 5 6 10 20 19 2 13 1 11 4 8 18 12 17 14 9
9 20
17 19
1 13
5 19
18 18
6 8
6 14
3 16
6 16
12 17
9 11
9 20
7 20
3 18
10 13
2 8
6 17
5 7
7 15
3 8
11 13
13 18
6 15
8 18
5 10
6 8
13 20
6 7
10 13
6 20
10 12
12 18
9 12
4 12
16 18
2 5
1 11
3 10
13 18
6 20
2 4
3 8
13 20
17 20
3 13
1 10
1 15
1...

output:

result:

ok 1000 numbers

Test #13:

score: 0

Accepted

time: 0ms

memory: 9824kb

input:

20 1337
10 3 6 8 7 15 4 5 9 19 17 13 1 18 12 16 20 2 11 14
10 14
4 5
9 11
7 14
2 8
7 18
11 18
9 12
2 6
8 15
11 18
12 16
19 19
8 19
12 16
4 11
2 18
1 6
15 19
2 12
4 9
3 5
16 20
10 14
3 9
10 10
7 17
6 11
8 10
3 4
6 18
7 12
1 15
7 16
16 17
3 16
6 12
4 15
10 17
13 19
4 20
18 19
13 14
3 16
8 10
3 16
1 14...

output:

result:

ok 1337 numbers

Test #14:

score: -100

Wrong Answer

time: 0ms

memory: 14964kb

input:

1000 1000
40 954 881 24 748 110 805 978 860 472 882 621 530 586 488 928 150 443 553 402 177 702 871 214 778 7 489 874 812 754 90 806 206 60 283 243 416 720 650 539 763 588 570 114 658 396 19 970 372 743 587 885 527 296 3 900 313 968 772 280 691 349 37 178 714 49 122 823 143 632 662 387 88 176 400 63...

output:

result:

wrong answer 1st numbers differ - expected: '91858', found: '91620'