QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722545#5543. The Only ModeuzumakiWA 653ms9140kbC++143.0kb2024-11-07 19:29:202024-11-07 19:29:20

Judging History

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

  • [2024-11-07 19:29:20]
  • 评测
  • 测评结果:WA
  • 用时:653ms
  • 内存:9140kb
  • [2024-11-07 19:29:20]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using std::cin;
using std::cout;

using i64 = long long;

const int nx = 1e5;

int n;
int a[nx + 5];

int bid[4], b[4][nx * 2 + 5];
int r0[nx * 2 + 5], r1[nx * 2 + 5], r2[nx * 2 + 5];
bool vis[nx + 5];
int ans[nx + 5];

void cdq1(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq1(l, mid), cdq1(mid + 1, r);
    
    int pl = l, pr = mid + 1, p1 = l - 1, mi = n + 1;
    while (pl <= mid && pr <= r) {
        if (b[2][r1[pl]] <= b[2][r1[pr]]) {
            r2[++p1] = r1[pl++];
            if (!vis[r2[p1]] && r2[p1] <= n) mi = std::min(mi, r2[p1]);
        }else {
            r2[++p1] = r1[pr++];
            if (vis[r2[p1]] && r2[p1] > n)
                ans[r2[p1] - n] = std::min(ans[r2[p1] - n], mi);
        }
    }
    while (pl <= mid) r2[++p1] = r1[pl++];
    while (pr <= r) {
        r2[++p1] = r1[pr++];
        if (vis[r2[p1]] && r2[p1] > n)
            ans[r2[p1] - n] = std::min(ans[r2[p1] - n], mi);
    }
    for (int i = l; i <= r; ++i) r1[i] = r2[i];
    
}

void cdq0(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq0(l, mid), cdq0(mid + 1, r);
    
    int pl = l, pr = mid + 1, p1 = l - 1;
    while (pl <= mid && pr <= r) {
        if (b[1][r0[pl]] <= b[1][r0[pr]]) r1[++p1] = r0[pl++], vis[r1[p1]] = false;
        else r1[++p1] = r0[pr++], vis[r1[p1]] = true;
    }
    while (pl <= mid) {
        r1[++p1] = r0[pl++];
        vis[r1[p1]] = false;
    }
    while (pr <= r) {
        r1[++p1] = r0[pr++];
        vis[r1[p1]] = true;
    }
    for (int i = l; i <= r; ++i) r0[i] = r1[i];
    cdq1(l, r);
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], r0[i] = i, r0[i + n] = i + n, ans[i] = n + 1;

    for (int k = 0; k < 4; ++k) {
        int bidn = 0;
        for (int i = 0; i < 4; ++i) if (i != k) bid[i] = bidn++;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 3; ++j) b[j][i] = 0;
            if (a[i] == k) {
                for (int j = 0; j < 3; ++j) b[j][i] = 1;
            }else b[bid[a[i]]][i] = -1;
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 1; j <= n; ++j) {
                b[i][j] += b[i][j - 1];
                b[i][j + n] = b[i][j] - 1;
            }
        }
        std::sort(r0, r0 + n * 2 + 1, [&](int x, int y) {
            if (b[0][x] != b[0][y])
                return b[0][x] < b[0][y];
            if (b[1][x] != b[1][y])
                return b[1][x] < b[1][y];
            if (b[2][x] != b[2][y])
                return b[2][x] < b[2][y];
            return x < y;
        });
        
        for (int i = 0; i <= n; ++i) vis[i] = false;
        cdq0(0, n * 2);

        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (ans[i] <= i) res = std::max(res, i - ans[i]);
            ans[i] = n + 1;
        }
        cout << res << " ";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7740kb

input:

7
1 2 2 0 3 0 3

output:

4 1 5 3 

result:

ok single line: '4 1 5 3 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 7736kb

input:

12
2 0 1 0 2 1 1 0 2 3 3 3

output:

4 9 1 9 

result:

ok single line: '4 9 1 9 '

Test #3:

score: 0
Accepted
time: 1ms
memory: 7732kb

input:

2
0 2

output:

1 0 1 0 

result:

ok single line: '1 0 1 0 '

Test #4:

score: 0
Accepted
time: 1ms
memory: 7676kb

input:

12
3 0 2 2 1 0 2 1 3 3 2 3

output:

1 5 11 8 

result:

ok single line: '1 5 11 8 '

Test #5:

score: 0
Accepted
time: 1ms
memory: 7768kb

input:

1
1

output:

0 1 0 0 

result:

ok single line: '0 1 0 0 '

Test #6:

score: 0
Accepted
time: 21ms
memory: 7808kb

input:

4207
3 1 0 3 2 0 3 1 1 1 1 3 0 1 1 0 2 2 3 0 1 1 0 1 0 2 0 1 0 0 3 3 1 0 1 3 3 0 2 0 2 0 1 0 2 3 2 3 0 0 0 0 1 2 1 2 0 2 2 0 3 3 2 2 0 2 2 0 3 0 1 3 1 1 0 2 3 0 1 2 1 2 0 0 1 1 0 3 3 2 0 2 1 3 0 1 0 3 0 0 0 2 2 2 0 1 1 0 3 1 1 3 3 2 2 1 3 3 1 3 2 0 2 3 2 2 1 0 2 3 0 1 0 0 1 1 1 3 3 1 3 3 3 0 0 0 3 2...

output:

2330 1520 4207 1359 

result:

ok single line: '2330 1520 4207 1359 '

Test #7:

score: -100
Wrong Answer
time: 653ms
memory: 9140kb

input:

89925
0 0 0 3 0 3 0 2 3 2 3 1 0 0 0 2 2 1 3 3 0 0 1 0 0 3 0 1 0 0 1 1 0 0 1 2 1 3 1 2 1 2 2 1 0 2 2 3 0 0 1 0 2 3 2 3 0 0 1 0 0 1 2 1 3 0 0 0 2 1 1 0 1 3 2 2 0 0 2 3 2 3 3 1 3 3 0 2 0 2 2 0 2 1 3 0 1 1 0 0 1 0 3 1 2 2 2 0 2 0 2 3 2 0 0 2 3 3 1 0 1 2 2 2 1 2 0 0 3 2 3 0 1 1 3 3 0 0 0 3 0 2 0 0 2 3 1 ...

output:

89925 49888 75725 39523 

result:

wrong answer 1st lines differ - expected: '89925 49888 75725 38162', found: '89925 49888 75725 39523 '