Submission #983377

#TimeUsernameProblemLanguageResultExecution timeMemory
983377GhettoSequence (APIO23_sequence)C++17
12 / 100
1292 ms91280 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int MAX_N = 5e5 + 5, MIN_SCORE = -5e5 - 5, MAX_SCORE = 1e6 + 5; int n; int a[MAX_N]; int lo_sum[MAX_N], hi_sum[MAX_N], val_sum[MAX_N]; int lo_score[MAX_N], hi_score[MAX_N]; unordered_map<int, vector<int>> inds; // NOTE: we still must take from i + 1 void precomp(int val) { inds.clear(); for (int i = 1; i <= n; i++) { lo_sum[i] = lo_sum[i - 1] + (a[i] < val); hi_sum[i] = hi_sum[i - 1] + (a[i] > val); val_sum[i] = val_sum[i - 1] + (a[i] == val); lo_score[i] = 2 * lo_sum[i] - i, hi_score[i] = 2 * hi_sum[i] - i; inds[lo_score[i - 1]].push_back(i - 1); if (i == n) inds[lo_score[i]].push_back(i); // cout << i << ": " << lo_score[i] << " " << hi_score[i] << endl; } } int st[5 * (MAX_SCORE - MIN_SCORE)]; void update(int i, int x, int u = 1, int lo = MIN_SCORE, int hi = MAX_SCORE) { if (i < lo || i > hi) return; if (lo == hi) { st[u] = max(st[u], x); return; } int mid = floor((lo + hi) / (double) 2); update(i, x, 2 * u, lo, mid), update(i, x, 2 * u + 1, mid + 1, hi); st[u] = max(st[2 * u], st[2 * u + 1]); } int query(int l, int r, int u = 1, int lo = MIN_SCORE, int hi = MAX_SCORE) { if (r < lo || l > hi) return 0; if (l <= lo && hi <= r) return st[u]; int mid = floor((lo + hi) / (double) 2); return max(query(l, r, 2 * u, lo, mid), query(l, r, 2 * u + 1, mid + 1, hi)); } int solve_val(int val) { // cout << "VALUE " << val << ": " << endl; for (int u = 0; u < 5 * (MAX_SCORE - MIN_SCORE); u++) st[u] = 0; precomp(val); int ans = 0; for (int x = MIN_SCORE; x <= MAX_SCORE; x++) { if (inds.count(x) == 0) continue; // cout << "SCORE " << x << ": "; for (int y : inds[x]) { // cout << y << " "; update(hi_score[y], y); } for (int y : inds[x]) { int resp = query(MIN_SCORE, hi_score[y]); ans = max(ans, val_sum[resp] - val_sum[y]); } // cout << endl; } return ans; } int sequence(int tmp_n, vector<int> tmp_a) { n = tmp_n; for (int i = 0; i < n; i++) a[i + 1] = tmp_a[i]; int ans = 0; for (int x : {1, 2, 3}) ans = max(ans, solve_val(x)); 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...