| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 982031 | FZ_Melo | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[100000];
int mat[2001][2001];
int ps[2001][2001];
int stmin[2001][13];
int stmax[2000][12];
int loga(int x){
int cnt=0;
while((1<<(cnt+1))<=x)
cnt++;
return cnt;
}
int minimo(int l, int r, int t){
int x=loga(t);
return min(stmin[l][x], stmin[r-(1<<x)+1][x]);
}
int maximo(int l, int r, int t){
int x=loga(t);
return max(stmax[l][x], stmax[r-(1<<x)+1][x]);
}
int bs(int l, int r, int x, int p1, int p2, int mini, int maxi){
int mid;
while(l<r){
mid=(l+r+1)/2;
if(ps[p2+1][mid]-ps[p1][mid]-(ps[p2+1][mini-1]-ps[p1][mini-1])<=x)
l=mid;
else
r=mid-1;
}
return l;
}
int calcula(int l, int r){
int t=r-l+1;
int mini=minimo(l, r, t);
int maxi=maximo(l, r, t);
int med=bs(mini, maxi, t/2+(t%2==1), l, r, mini, maxi);
if(ps[r+1][med]-ps[l][med]-(ps[r+1][mini-1]-ps[l][mini-1])<t/2+(t%2==1))
med++;
int cnt1=ps[r+1][med]-ps[l][med]-(ps[r+1][med-1]-ps[l][med-1]), cnt2=0;
if(t%2==0 && ps[r+1][med]-ps[l][med]-(ps[r+1][mini-1]-ps[l][mini-1])==t/2){
cnt2=ps[r+1][med+1]-ps[l][med+1]-(ps[r+1][med]-ps[l][med]);
}
return max(cnt1, cnt2);
}
int sequence(int N, std::vector<int> A) {
n=N;
int logn=loga(n);
for(int i=0; i<n; i++)
arr[i]=A[i];
mat[0][arr[0]]++;
for(int i=1; i<n; i++){
for(int j=0; j<=n; j++){
mat[i][j]=mat[i-1][j];
}
mat[i][arr[i]]++;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
ps[i][j]=ps[i][j-1]+mat[i-1][j];
}
}
for(int i=0; i<n; i++){
stmin[i][0]=arr[i];
stmax[i][0]=arr[i];
}
for(int k=1; k<=logn; k++){
for(int i=0; i<n; i++){
stmin[i][k]=min(stmin[i][k-1], stmin[i+(1<<(k-1))][k-1]);
stmax[i][k]=max(stmax[i][k-1], stmax[i+(1<<(k-1))][k-1]);
}
}
int ans=1;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
int x=calcula(i, j);
ans=max(ans, x);
}
}
return ans;
}