제출 #770164

#제출 시각아이디문제언어결과실행 시간메모리
770164gg123_pe서열 (APIO23_sequence)C++17
63 / 100
2072 ms71284 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; #define f(i,a,b) for(int i = a; i < b; i++) #define fa(i,a,b) for(int i = a; i >= b; i--) const int N = 5e5 + 5; const int inf = 2e9; int n; vector <int> pos[N]; struct ST{ ii st[4*N], zero = {inf, -inf}; int lazy[4*N]; ii merge(ii a, ii b){ return {min(a.first, b.first), max(a.second, b.second)}; } void down(int id){ lazy[id<<1] += lazy[id], lazy[id<<1|1] += lazy[id]; st[id<<1].first += lazy[id], st[id<<1].second += lazy[id]; st[id<<1|1].first += lazy[id], st[id<<1|1].second += lazy[id]; lazy[id] = 0; } void Upd(int id, int l, int r, int x, int y, int val){ if(r < x or y < l) return; if(x <= l and r <= y){ lazy[id] += val; st[id].first += val, st[id].second += val; return; } down(id); int m = (l+r)>>1; Upd(id<<1, l, m, x, y, val), Upd(id<<1|1, m+1, r, x, y, val); st[id] = merge(st[id<<1], st[id<<1|1]); } ii query(int id, int l, int r, int x, int y){ if(r < x or y < l) return zero; if(x <= l and r <= y) return st[id]; down(id); int m = (l+r)>>1; return merge(query(id<<1, l, m, x, y), query(id<<1|1, m+1, r, x, y)); } int val(int pos){ if(pos == 0) return 0; return query(1, 1, n, pos, pos).first; } void upd(int node, int val){ Upd(1, 1, n, node, n, val); } }st[2]; int sign(int x){ if(x == 0) return x; return x / abs(x); } bool check(int x, int y){ int VL1 = st[0].val(x-1), VR1 = st[0].val(y), sum1 = VR1 - VL1; int VL2 = st[1].val(x-1), VR2 = st[1].val(y), sum2 = VR2 - VL2; int maL = 0, maR = 0; int miL = 0, miR = 0; if(x != 1){ ii C1 = st[0].query(1, 1, n, 1, x-1); ii C2 = st[1].query(1, 1, n, 1, x-1); maL = max(0, max(VL1, VL1 - C1.first)); miL = min(0, min(VL2, VL2 - C2.second)); } if(y != n){ ii C1 = st[0].query(1, 1, n, y+1, n); ii C2 = st[1].query(1, 1, n, y+1, n); maR = max(0, C1.second - VR1); miR = min(0, C2.first - VR2); } return sign(sum1 + maL + maR) * sign (sum2 + miL + miR) <= 0; } int sequence(int Ni, vector<int> A) { n = Ni; f(i,0,n){ pos[A[i]].push_back(i+1); } f(i,1,n+1){ st[0].upd(i, 1); st[1].upd(i, 1); } int ans = 1; f(i,1,n+1){ int len = pos[i].size(); for(int x: pos[i]){ st[1].upd(x, -2); } int r = -1; f(j,0,len){ r = max(r, j); while(r < len and check(pos[i][j], pos[i][r])) r++; r--; ans = max(ans, r - j + 1); } for(int x: pos[i]){ st[0].upd(x, -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...