제출 #1111950

#제출 시각아이디문제언어결과실행 시간메모리
1111950abczz서열 (APIO23_sequence)C++17
50 / 100
2069 ms205048 KiB
#include "sequence.h" #include <iostream> #include <vector> #include <array> #define ll long long using namespace std; vector <ll> V[500000]; struct SegTree{ ll st[4][2000000], lazy[4][2000000]; void push(ll id) { for (int i=0; i<4; ++i) { st[i][id*2] += lazy[i][id]; st[i][id*2+1] += lazy[i][id]; lazy[i][id*2] += lazy[i][id]; lazy[i][id*2+1] += lazy[i][id]; lazy[i][id] = 0; } } void update(ll id, ll l, ll r, ll ql, ll qr, ll z, ll w) { if (qr < l || r < ql) return; else if (ql <= l && r <= qr) { st[z][id] += w; lazy[z][id] += w; return; } push(id); ll mid = (l+r)/2; update(id*2, l, mid, ql, qr, z, w); update(id*2+1, mid+1, r, ql, qr, z, w); for (int i=0; i<4; ++i) st[i][id] = max(st[i][id*2], st[i][id*2+1]); st[1][id] = min(st[1][id*2], st[1][id*2+1]); } ll query(ll id, ll l, ll r, ll ql, ll qr, ll z) { if (qr < l || r < ql) return (z != 1 ? -1e18 : 1e18); else if (ql <= l && r <= qr) return st[z][id]; push(id); ll mid = (l+r)/2; return (z != 1 ? max(query(id*2, l, mid, ql, qr, z), query(id*2+1, mid+1, r, ql, qr, z)) : min(query(id*2, l, mid, ql, qr, z), query(id*2+1, mid+1, r, ql, qr, z))); } ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll z, ll w) { if (qr < l || r < ql) return -1e18; else if (ql <= l && r <= qr) { ll mid = (l+r)/2; push(id); if (st[z][id] >= w) { if (l == r) return l; if (st[z][id*2+1] >= w) return queryR(id*2+1, mid+1, r, ql, qr, z, w); else return queryR(id*2, l, mid, ql, qr, z, w); } return -1e18; } push(id); ll mid = (l+r)/2, res = queryR(id*2+1, mid+1, r, ql, qr, z, w); if (res >= 0) return res; return queryR(id*2, l, mid, ql, qr, z, w); } }ST; ll a, b, c, d, s, f; int sequence(int N, std::vector<int> A) { f = 1; for (int i=0; i<N; ++i) { --A[i]; V[A[i]].push_back(i); ST.update(1, 0, N-1, i, N-1, 0, -1); ST.update(1, 0, N-1, i, N-1, 1, -1); ST.update(1, 0, N-1, i, N-1, 2, -1); ST.update(1, 0, N-1, i, N-1, 3, 1); } for (int i=0; i<5e5; ++i) { for (auto u : V[i]) { ST.update(1, 0, N-1, u, N-1, 0, 1); ST.update(1, 0, N-1, u, N-1, 1, 1); ST.update(1, 0, N-1, u, N-1, 2, 2); } ll p = 0, k = 0, s; for (auto u : V[i]) { if (p < u) { auto tmp = ST.query(1, 0, N-1, u, u, 0); a = tmp - min((p == 0 ? 0LL : (ll)1e18), ST.query(1, 0, N-1, max(0LL, p-1), u, 1)), b = -(tmp-max((p == 0 ? 0LL : (ll)-1e18), ST.query(1, 0, N-1, max(0LL, p-1), u, 0))); } else a = b = 0; a = max(0LL, a), b = max(0LL, b); if (u) s = ST.query(1, 0, N-1, u-1, u-1, 2); else s = 0; c = ST.queryR(1, 0, N-1, u, N-1, 2, -a+s); if (u) s = ST.query(1, 0, N-1, u-1, u-1, 3); else s = 0; d = ST.queryR(1, 0, N-1, u, N-1, 3, -b+s); s = min(c, d); if (s != -1) { auto it = lower_bound(V[i].begin(), V[i].end(), s+1); it = prev(it); f = max(f, it-V[i].begin()-k+1); } p = u+1, ++k; } for (auto u : V[i]) { ST.update(1, 0, N-1, u, N-1, 0, 1); ST.update(1, 0, N-1, u, N-1, 1, 1); ST.update(1, 0, N-1, u, N-1, 3, -2); } } return f; }
#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...