Submission #1201131

#TimeUsernameProblemLanguageResultExecution timeMemory
1201131aykhnSequence (APIO23_sequence)C++20
7 / 100
835 ms52248 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; struct DATA { int s = 0, mxp = 0, mxs = 0, mnp = 0, mns = 0; }; const int MXN = 5e5 + 5; DATA st[MXN << 2]; DATA combine(DATA x, DATA y) { return {x.s + y.s, max(x.mxp, x.s + y.mxp), max(y.mxs, y.s + x.mxs), min(x.mnp, x.s + y.mnp), min(y.mns, y.s + x.mns)}; } void upd(int l, int r, int x, int ind, int val) { if (l == r) { st[x] = {val, max(0, val), max(0, val), min(0, val), min(0, val)}; return; } int mid = (l + r) >> 1; if (ind <= mid) upd(l, mid, 2*x, ind, val); else upd(mid + 1, r, 2*x + 1, ind, val); st[x] = combine(st[2*x], st[2*x + 1]); } DATA get(int l, int r, int x, int lx, int rx) { if (lx > rx) return {0, 0, 0, 0, 0}; if (l > rx || r < lx) return {0, 0, 0, 0, 0}; if (l >= lx && r <= rx) return st[x]; int mid = (l + r) >> 1; return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx)); } int sequence(int N, vector<int> A) { vector<int> idx[N + 1]; for (int i = 0; i < N; i++) idx[A[i]].push_back(i); for (int i = 0; i < N; i++) upd(0, N - 1, 1, i, 1); int res = 0; for (int val = 1; val <= N; val++) { vector<int> &v = idx[val]; for (int &i : v) upd(0, N - 1, 1, i, 1); for (int r = 0, l = 0; r < v.size(); r++) { while (l <= r) { DATA x = get(0, N - 1, 1, v[l], v[r]); // A = a, B = x - y int A = r - l + 1; int B = x.s; DATA L = get(0, N - 1, 1, 0, v[l] - 1); DATA R = get(0, N - 1, 1, v[r], N - 1); int mn = B + L.mns + R.mnp, mx = B + L.mxs + R.mxp; if ((mn <= 0 && 0 <= mx) || min(abs(mn), abs(mx)) <= A) { res = max(res, A); break; } l++; } } for (int &i : v) upd(0, N - 1, 1, i, -1); } return res; } /* 9 1 1 2 3 4 3 2 1 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...