제출 #752336

#제출 시각아이디문제언어결과실행 시간메모리
752336aryan12서열 (APIO23_sequence)C++17
12 / 100
333 ms26632 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5 + 5, INF = 1e18; int seg[N * 2 * 4]; int32_t print_occ(int val, vector<int32_t> &x) { int ans = 0; for(int i: x) { ans += (i == val); } return ans; } void Build(int l, int r, int pos) { seg[pos] = INF; if(l == r) { return; } int mid = (l + r) / 2; Build(l, mid, pos * 2); Build(mid + 1, r, pos * 2 + 1); } void Update(int l, int r, int pos, int qpos, int qval) { if(l == r) { seg[pos] = min(seg[pos], qval); return; } int mid = (l + r) / 2; if(qpos <= mid) { Update(l, mid, pos * 2, qpos, qval); } else { Update(mid + 1, r, pos * 2 + 1, qpos, qval); } seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]); } int Query(int l, int r, int pos, int ql, int qr) { if(ql <= l && r <= qr) { return seg[pos]; } if(ql > r || l > qr) { return INF; } int mid = (l + r) / 2; return min(Query(l, mid, pos * 2, ql, qr), Query(mid + 1, r, pos * 2 + 1, ql, qr)); } int32_t sequence(int32_t n, vector<int32_t> a) { vector<int32_t> b = a; sort(b.begin(), b.end()); int median1 = (n - 1) / 2, median2 = n / 2; if(b[median1] != 2) { return print_occ(b[median1], b); } if(b[median2] != 2) { return print_occ(b[median2], b); } int ans = print_occ(b[median2], b); for(int check = 1; check <= 3; check += 2) { vector<int> pref(n, 0); Build(0, 2 * n, 1); int cur_cnt = n; Update(0, 2 * n, 1, cur_cnt, -1); // cout << "check = " << check << ", i = -1, cur_cnt = " << cur_cnt << "\n"; for(int i = 0; i < n; i++) { cur_cnt = (a[i] == check) ? cur_cnt + 1 : cur_cnt - 1; // cout << "check = " << check << ", i = " << i << ", cur_cnt = " << cur_cnt << "\n"; pref[i] = (i == 0) ? 0 : pref[i - 1]; if(a[i] == check) { pref[i] += 1; } Update(0, 2 * n, 1, cur_cnt, i); int min_ans = Query(0, 2 * n, 1, 0, cur_cnt); if(min_ans == INF) { continue; } int this_ans = (min_ans == -1) ? pref[i] : pref[i] - pref[min_ans]; ans = max(ans, this_ans); } } 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...