| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127831 |
2019-07-10T06:56:03 Z |
임유진(#3111) |
JOI15_aaqqz (JOI15_aaqqz) |
C++14 |
|
2 ms |
636 KB |
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 3005
int N, C;
int ans;
int S[MAXN];
vector<int> p[MAXN];
int lr[MAXN][MAXN];
int seg[4 * MAXN];
void updseg(int idx, int l, int r, int x, int y) {
if(idx == 1) {
//printf("updseg(x = %d, y = %d)\n", x, y);
//if(x == 9) printf("************************\n");
}
if(l == r) seg[idx] = y;
else {
int m = (l + r) / 2;
if(x <= m) updseg(idx * 2, l, m, x, y);
else updseg(idx * 2 + 1, m + 1, r, x, y);
seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]);
}
}
int gseg(int idx, int l, int r, int x, int y) {
//if(idx == 1) printf("gseg(x = %d, y = %d)\n", x, y);
//if(x == 9 && y == 9) printf("idx = %d, l = %d, r = %d********\n", idx, l, r);
if(x <= l && r <= y) return seg[idx];
if(r < x || y < l) return 0;
int m = (l + r) / 2;
return max(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y));
}
void solve() {
for(int i = 1; i <= C; i++) p[i].clear();
for(int i = 1; i <= N; i++) p[S[i]].push_back(i);
for(int i = 1; i <= C; i++) ans = max(ans, (int)p[i].size());
for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) lr[i][j] = S[i] == S[j] ? lr[i - 1][j + 1] + 1 : 0;
/*
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) printf("%d ", lr[i][j]);
printf("\n");
}
*/
for(int i = 1; i <= N; i++) updseg(1, 1, N, i, S[i]);
for(int i = 1; i < 2 * N; i++) {
if(i > N && S[i - N] != S[i - N + 1]) continue;
int l = i <= N ? lr[i][i] : lr[i - N][i - N + 1];
int k = i <= N ? i - l + 1 : i - N - l + 1;
int tt = k;
ans = max(ans, i <= N ? 2 * l - 1 : 2 * l);
for(int j = (i <= N ? i : i - N + 1) + l; j <= N; j++) {
//printf("i = %d, j = %d, l = %d, k = %d, tt = %d\n", i, j, l, k, tt);
if(j != i + l && S[j] > S[j - 1]) break;
int g = gseg(1, 1, N, k, i <= N ? i - l : i - N - l);
//printf("g = %d\n", g);
if(g > S[j]) break;
else if(g < S[j]) {
int t = lower_bound(p[S[j]].begin(), p[S[j]].end(), k) - p[S[j]].begin();
//printf("t = %d\n", t);
if(t == 0 || gseg(1, 1, N, p[S[j]][t - 1], k - 1) > S[j]) break;
tt = k = p[S[j]][t - 1];
updseg(1, 1, N, tt, 0);
}
else if(g == S[j]) {
int t = lower_bound(p[S[j]].begin(), p[S[j]].end(), (S[j] == S[j - 1] ? tt : i - l + 1)) - p[S[j]].begin();
tt = p[S[j]][t - 1];
updseg(1, 1, N, tt, 0);
}
if(k + j == (i <= N ? i * 2 : i * 2 - 2 * N + 1)) ans = max(ans, j - k + 1 + lr[k - 1][j + 1]);
ans = max(ans, i <= N ? 2 * (j - i) + 1 : 2 * (j - i + N));
}
for(int j = k; j <= (i <= N ? i - l : i - N - l); j++) updseg(1, 1, N, j, S[j]);
//printf("ans = %d\n", ans);
}
//printf("\n");
for(int i = 1; i < N; i++) {
int k = i;
int tt = k;
int mx = 0, mxcnt = 0;
if(S[i] > S[i + 1]) {
mx = i;
mxcnt = 1;
updseg(1, 1, N, i, 0);
}
for(int j = i + 1; j <= N; j++) {
//printf("i = %d, j = %d, k = %d, tt = %d, mx = %d, mxcnt = %d\n", i, j, k, tt, mx, mxcnt);
if(j != i + 1 && S[j] > S[j - 1]) break;
int g = gseg(1, 1, N, k, i);
//printf("g = %d\n", g);
if(g > S[j]) break;
else if(g < S[j]) {
int t = lower_bound(p[S[j]].begin(), p[S[j]].end(), k) - p[S[j]].begin();
//printf("t = %d\n", t);
if(t == 0) break;
k = p[S[j]][t - 1];
int gg = gseg(1, 1, N, k, i);
if(gg > S[i + 1] && mx == 0) {
int tt = lower_bound(p[gg].begin(), p[gg].end(), k) - p[gg].begin();
mx = p[gg][tt - 1];
for(int a = tt; a < p[gg].size() && p[gg][a] <= i; a++) {
updseg(1, 1, N, p[gg][a], 0);
mxcnt++;
}
}
if(gseg(1, 1, N, k, i) > S[j]) break;
updseg(1, 1, N, p[S[j]][t - 1], 0);
}
else if(g == S[j]) {
int t = lower_bound(p[S[j]].begin(), p[S[j]].end(), (j != i + 1 && S[j] == S[j - 1] ? tt : i + 1)) - p[S[j]].begin();
k = tt = p[S[j]][t - 1];
updseg(1, 1, N, tt, 0);
}
if(k + j == i * 2 + mxcnt - 1) ans = max(ans, j - k + 1 + lr[k - 1][j + 1]);
ans = max(ans, 2 * j - 2 * i + mxcnt);
}
for(int j = k; j <= i; j++) updseg(1, 1, N, j, S[j]);
//printf("ans = %d\n", ans);
}
//printf("\n");
}
int main() {
scanf("%d%d", &N, &C);
for(int i = 1; i <= N; i++) scanf("%d", S + i);
solve();
for(int i = 1; i <= N / 2; i++) swap(S[i], S[N + 1 - i]);
for(int i = 1; i <= N; i ++) S[i] = C + 1 - S[i];
solve();
printf("%d", ans);
return 0;
}
Compilation message
aaqqz.cpp: In function 'void solve()':
aaqqz.cpp:111:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = tt; a < p[gg].size() && p[gg][a] <= i; a++) {
~~^~~~~~~~~~~~~~
aaqqz.cpp: In function 'int main()':
aaqqz.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &C);
~~~~~^~~~~~~~~~~~~~~~
aaqqz.cpp:136:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= N; i++) scanf("%d", S + i);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
