제출 #750019

#제출 시각아이디문제언어결과실행 시간메모리
750019Cookie서열 (APIO23_sequence)C++17
100 / 100
1139 ms64636 KiB
#include<bits/stdc++.h> #include "sequence.h" #include<fstream> using namespace std; ifstream fin("VNOICUP.INP"); ofstream fout("VNOICUP.OUT"); #define sz(a) (int)a.size() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> const int mxn = 5e5; const ll prec = 1e-6; struct ST{ // range min prefix, range update int st[4 * mxn + 1], lz[4 * mxn + 1]; void push(int nd, int l, int mid, int r){ lz[nd << 1] += lz[nd]; lz[nd << 1 | 1] += lz[nd]; st[nd << 1] += lz[nd]; st[nd << 1 | 1] += lz[nd]; lz[nd] = 0; } void init(int nd, int l, int r){ if(l == r){ st[nd] = -l; return; } int mid = (l + r) >> 1; init(nd << 1, l, mid); init(nd << 1 | 1, mid + 1, r); st[nd] = min(st[nd << 1], st[nd << 1 | 1]); } void upd(int nd, int l, int r, int ql, int qr, int v){ if(ql > r || qr < l)return; if(ql <= l && qr >= r){ st[nd] += v; lz[nd] += v; return; } int mid = (l + r) >> 1; push(nd, l, mid, r); upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v); st[nd] = min(st[nd << 1], st[nd << 1 | 1]); } int get(int nd, int l, int r, int ql, int qr){ if(ql > r || qr < l)return(1e9); if(ql <= l && qr >= r)return(st[nd]); int mid = (l + r) >> 1; push(nd, l, mid, r); return(min(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr))); } }; struct ST2{ // range max prefix, range update int st[4 * mxn + 1], lz[4 * mxn + 1]; void push(int nd, int l, int mid, int r){ lz[nd << 1] += lz[nd]; lz[nd << 1 | 1] += lz[nd]; st[nd << 1] += lz[nd]; st[nd << 1 | 1] += lz[nd]; lz[nd] = 0; return; } void init(int nd, int l, int r){ if(l == r){ st[nd] = -l; return; } int mid = (l + r) >> 1; init(nd << 1, l, mid); init(nd << 1 | 1, mid + 1, r); st[nd] = max(st[nd << 1], st[nd << 1 | 1]); } void upd(int nd, int l, int r, int ql, int qr, int v){ if(ql > r || qr < l)return; if(ql <= l && qr >= r){ st[nd] += v; lz[nd] += v; return; } int mid = (l + r) >> 1; push(nd, l, mid, r); upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v); st[nd] = max(st[nd << 1], st[nd << 1 | 1]); } int get(int nd, int l, int r, int ql, int qr){ if(ql > r || qr < l)return(-1e9); if(ql <= l && qr >= r)return(st[nd]); int mid = (l + r) >> 1; push(nd, l, mid, r); return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr))); } }; ST large, equa; ST2 large2, equa2; vt<int>comp[mxn + 1]; int sequence(int n, std::vector<int> a) { large.init(1, 0, n); equa.init(1, 0, n); large2.init(1, 0, n); equa2.init(1, 0, n); for(int i = 0; i < n; i++){ comp[a[i]].pb(i + 1); } int ans = 1; for(int i = 1; i <= n; i++){ for(auto j: comp[i]){ equa.upd(1, 0, n, j, n, 2); equa2.upd(1, 0, n, j, n,2); } int r = 1; for(int j = 0; j < sz(comp[i]) - 1; j++){ r = max(r, j + 1); while(r < sz(comp[i])){ ll lar = large.get(1, 0, n, comp[i][r], n) - large2.get(1, 0, n, 0, comp[i][j] - 1); ll equ = equa2.get(1, 0, n, comp[i][r], n) - equa.get(1, 0, n, 0, comp[i][j] - 1); //if(i == 1 && j = 0) if(equ >= 0 && lar <= 0){ r++; }else{ break; } } ans = max(ans, r - j); } for(auto j: comp[i]){ large.upd(1, 0, n, j, n,2); large2.upd(1, 0, n, j, n,2); } } 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...