Submission #982028

#	Time	Username	Problem	Language	Result	Execution time	Memory
982028		FZ_Melo	Sequence (APIO23_sequence)	C++17	0 / 100	39 ms	9096 KiB

sequence

#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=0;
  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;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18