QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722545 | #5543. The Only Mode | uzumaki | WA | 653ms | 9140kb | C++14 | 3.0kb | 2024-11-07 19:29:20 | 2024-11-07 19:29:20 |
Judging History
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 '