Submission #872296

#TimeUsernameProblemLanguageResultExecution timeMemory
872296green_gold_dogSequence (APIO23_sequence)C++17
50 / 100
2076 ms94296 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; typedef int ll; const ll INF = 1'000'000'000; struct segment_tree_min { vector<ll> tree, m; ll size; segment_tree_min(ll n) { size = n; tree.resize(size * 4, 0); m.resize(size * 4, 0); } void add(ll v, ll x) { tree[v] += x; m[v] += x; } void push(ll v) { add(v * 2, m[v]); add(v * 2 + 1, m[v]); m[v] = 0; } ll get(ll l, ll r) { return get(1, 0, size, l, r); } ll get(ll v, ll l, ll r, ll ql, ll qr) { if (ql <= l && r <= qr) { return tree[v]; } if (qr <= l || r <= ql) { return INF; } push(v); ll mid = (l + r) / 2; return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr)); } void add(ll l, ll r, ll x) { add(1, 0, size, l, r, x); } void add(ll v, ll l, ll r, ll ql, ll qr, ll x) { if (ql <= l && r <= qr) { add(v, x); return; } if (qr <= l || r <= ql) { return; } push(v); ll mid = (l + r) / 2; add(v * 2, l, mid, ql, qr, x); add(v * 2 + 1, mid, r, ql, qr, x); tree[v] = min(tree[v * 2], tree[v * 2 + 1]); } }; struct segment_tree_max { vector<ll> tree, m; ll size; segment_tree_max(ll n) { size = n; tree.resize(size * 4, 0); m.resize(size * 4, 0); } void add(ll v, ll x) { tree[v] += x; m[v] += x; } void push(ll v) { add(v * 2, m[v]); add(v * 2 + 1, m[v]); m[v] = 0; } ll get(ll l, ll r) { return get(1, 0, size, l, r); } ll get(ll v, ll l, ll r, ll ql, ll qr) { if (ql <= l && r <= qr) { return tree[v]; } if (qr <= l || r <= ql) { return -INF; } push(v); ll mid = (l + r) / 2; return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr)); } void add(ll l, ll r, ll x) { add(1, 0, size, l, r, x); } void add(ll v, ll l, ll r, ll ql, ll qr, ll x) { if (ql <= l && r <= qr) { add(v, x); return; } if (qr <= l || r <= ql) { return; } push(v); ll mid = (l + r) / 2; add(v * 2, l, mid, ql, qr, x); add(v * 2 + 1, mid, r, ql, qr, x); tree[v] = max(tree[v * 2], tree[v * 2 + 1]); } }; ll sequence(ll n, vector<ll> a) { segment_tree_min sti(n), stir(n); segment_tree_max sta(n), star(n); vector<vector<ll>> all(n); for (ll i = 0; i < n; i++) { sti.add(i, n, 1); sta.add(i, n, 1); stir.add(0, i + 1, 1); star.add(0, i + 1, 1); all[a[i] - 1].push_back(i); } ll ans = 0, ns = n; for (ll i = 0; i < n; i++) { for (auto j : all[i]) { sti.add(j, n, -1); sti.add(j, n, -1); stir.add(0, j + 1, -1); star.add(0, j + 1, -1); ns--; } ll lst = 0; for (ll j = 0; j < all[i].size(); j++) { ll x = all[i][j]; sti.add(x, n, 1); sta.add(x, n, -1); ll m = ns;// + (all[i].size() - j); ll mmi = stir.get(lst, all[i][j] + 1) - ns, mma = star.get(lst, all[i][j] + 1) - ns; ll ql = all[i][j], qr = n; ll v = 1, l = 0, r = n; while (r - l > 1) { sti.push(v); sta.push(v); ll mid = (l + r) / 2; if (mid < ql) { l = mid; v = v * 2 + 1; continue; } ll mi = sti.tree[v * 2 + 1] + mmi, ma = sta.tree[v * 2 + 1] + mma; if ((mi <= -1 && ma >= -1) || (mi <= 0 && ma >= 0) || (mi <= 1 && ma >= 1)) { v = v * 2 + 1; l = mid; } else { v = v * 2; r = mid; } } ans = max(ans, (ll)((lower_bound(all[i].begin(), all[i].end(), r) - all[i].begin()) - j)); lst = all[i][j] + 1; } for (auto j : all[i]) { sti.add(j, n, -1); sta.add(j, n, -1); stir.add(0, j + 1, -1); star.add(0, j + 1, -1); ns--; } } return ans; }

Compilation message (stderr)

sequence.cpp: In function 'll sequence(ll, std::vector<int>)':
sequence.cpp:132:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |                 for (ll j = 0; j < all[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~
sequence.cpp:136:28: warning: unused variable 'm' [-Wunused-variable]
  136 |                         ll m = ns;// + (all[i].size() - j);
      |                            ^
sequence.cpp:138:44: warning: unused variable 'qr' [-Wunused-variable]
  138 |                         ll ql = all[i][j], qr = n;
      |                                            ^~
#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...