# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
896317 | 2024-01-01T09:07:33 Z | vjudge1 | 서열 (APIO23_sequence) | C++17 | 0 ms | 0 KB |
#pragma GCC optimize("O3,unroll-loops"); #include <bits/stdc++.h> #include "sequence.h" using namespace std;const int LIM = 5e5+1; vector<int> bit(LIM,0); int n; void add(int p,int v) { for (int i=p;i<=n;i+=i&-i) bit[i]+=v; } int get(int p) { int ans = 0; for (int i=p;i>0;i-=i&-i) ans+=bit[i]; return ans; } int sequence(int N, std::vector<int> A) { n = N; vector<int> sme(N+1); vector<int> sm(N+1); for (int i=1;i<=N;i++) { add(A[i-1],1); sme[i] = get(A[i-1]); sm[i] = get(A[i-1]-1); } vector<int> poss[N+1]; for (int i=1;i<=n;i++) poss[A[i-1]].push_back(i); int l = 0; int r = N-1; while (l<=r) { int m = (l+r) >> 1; bool flag = 0; for (int i=1;i<=n;i++) { int sz = poss[i].size(); for (int j=0;j+m<sz;j++) { int smme = sme[poss[i][j+m]]-sme[poss[i][j]]+1; int smm = sm[poss[i][j+1]]-sm[poss[i][j]]; if (smme >= (poss[i][j+m]-poss[i][j]+2)/2 && smm < (poss[i][j+m]-poss[i][j]+2)/2) { flag = 1; } } } if (flag) l = m+1; else r = m-1; } return r+1; }