Submission #1190165

#TimeUsernameProblemLanguageResultExecution timeMemory
1190165kiritoSequence (APIO23_sequence)C++20
70 / 100
757 ms80716 KiB
#include <bits/stdc++.h> using namespace std; const int N = 510000; struct segtree { vector<int> vmn, vmx, lz; segtree() {} segtree(int n) { vmn = vmx = lz = vector<int>(4 * n + 1, 0); } void push(int v, int l, int r) { if (lz[v] == 0) return; vmn[v] += lz[v]; vmx[v] += lz[v]; if (l != r) { lz[v * 2 + 0] += lz[v]; lz[v * 2 + 1] += lz[v]; } lz[v] = 0; } void upd(int v, int l, int r, int ql, int qr, int x) { push(v, l, r); if (qr < l || r < ql) return; if (ql <= l && r <= qr) { lz[v] += x; push(v, l, r); return; } int mid = (l + r) / 2; upd(v * 2 + 0, l, mid, ql, qr, x); upd(v * 2 + 1, mid + 1, r, ql, qr, x); vmn[v] = min(vmn[v * 2 + 0], vmn[v * 2 + 1]); vmx[v] = max(vmx[v * 2 + 0], vmx[v * 2 + 1]); } int getmin(int v, int l, int r, int ql, int qr) { push(v, l, r); if (qr < l || r < ql) return (int)(1e18); if (ql <= l && r <= qr) return vmn[v]; int mid = (l + r) / 2; return min(getmin(v * 2 + 0, l, mid, ql, qr), getmin(v * 2 + 1, mid + 1, r, ql, qr)); } int getmax(int v, int l, int r, int ql, int qr) { push(v, l, r); if (qr < l || r < ql) return (int)(-1e18); if (ql <= l && r <= qr) return vmx[v]; int mid = (l + r) / 2; return max(getmax(v * 2 + 0, l, mid, ql, qr), getmax(v * 2 + 1, mid + 1, r, ql, qr)); } }; vector<int> pos[N]; int sequence(int n, vector<int> a) { vector<int> vals = a; sort(begin(vals), end(vals)); int m1 = vals[(n - 1) / 2]; int m2 = vals[n - (n - 1) / 2]; int cnt_m1 = 0, cnt_m2 = 0; for (int x : a) if (x == m1) cnt_m1++; else if (x == m2) cnt_m2++; int ans = max(cnt_m1, cnt_m2); for (int i = 0; i < n; i++) pos[a[i]].push_back(i + 1); segtree seg; seg = segtree(n + 1); for (int i = 1; i <= n; i++) seg.upd(1, 0, n, i, n, 1); for (int i = 1; i < m1; i++) { for (int j : pos[i]) seg.upd(1, 0, n, j, n, -2); int m = (int) pos[i].size(); vector<int> pmax(m), pmin(m); for (int j = 0; j < m; j++) { pmax[j] = seg.getmax(1, 0, n, 0, pos[i][j] - 1); pmin[j] = seg.getmin(1, 0, n, pos[i][j], n); } for (int j = 0; j < m; j++) ans = max(ans, (int) (upper_bound(begin(pmin), end(pmin), pmax[j]) - begin(pmin) - j)); } seg = segtree(n + 1); for (int i = 1; i <= n; i++) seg.upd(1, 0, n, i, n, -1); for (int i = n; i > m2; i--) { for (int j : pos[i]) seg.upd(1, 0, n, j, n, 2); int m = (int) pos[i].size(); vector<int> pmax(m), pmin(m); for (int j = 0; j < m; j++) { pmax[j] = -seg.getmin(1, 0, n, 0, pos[i][j] - 1); pmin[j] = -seg.getmax(1, 0, n, pos[i][j], n); } for (int j = 0; j < m; j++) ans = max(ans, (int) (upper_bound(begin(pmin), end(pmin), pmax[j]) - begin(pmin) - j)); } return ans; }
#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...