QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696995 | #9483. Maximize Array | gzy | WA | 3ms | 16140kb | C++14 | 1.2kb | 2024-11-01 09:31:31 | 2024-11-01 09:31:31 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
using ll = long long;
using db = double;
using ull = unsigned long long;
const int N = 1048576 + 7;
const int b = 133331;
int i, j, k, n, m, tp, x, y, K, to[N];
int st[N], p[N], g[N], c[N][21], s[N];
ull f[N][21];
void pt(int x) {
if(x == n + 1) return;
if(to[x] == x + 1) putchar(s[x] + '0'), putchar(' ');
pt(to[x]);
}
int main() {
scanf("%d%d", &n, &K);
for(i = 1; i <= n; i++) scanf("%d", &s[i]);
g[0] = 1;
for(i = 1; i < N; i++) g[i] = g[i-1] * b;
c[n][0] = n + 1, f[n][0] = s[n]; to[n] = n + 1;
for(i = 1; i < 21; i++) f[n][i] = s[n] * g[1<<i-1], c[n][i] = n + 1;
for(i = n - 1; i; i--) {
f[i][0] = s[i]; c[i][0] = i + 1; to[i] = i + 1;
for(j = 1; j < 21; j++) c[i][j] = c[c[i][j-1]][j-1];
for(j = 1; j < 21; j++) f[i][j] = f[i][j-1] * g[1<<j-1] + f[c[i][j-1]][j-1];
if(i + K > n) continue;
x = i, y = i + K;
for(j = 20; ~j; j--) if(f[x][j] == f[y][j]) x = c[x][j], y = c[y][j];
if(f[x][0] < f[y][0]) {
to[i] = i + K;
for(j = 0; j < 21; j++) c[i][j] = c[to[i]][j];
for(j = 0; j < 21; j++) f[i][j] = f[to[i]][j];
}
}
pt(1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 16112kb
input:
9 3 1 2 3 4 1 2 3 4 1
output:
4 4 1
result:
ok 3 tokens
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 16140kb
input:
6 1 1 6 4 2 3 5
output:
1 6 4 2 3 5
result:
wrong answer 1st words differ - expected: '6', found: '1'