oj.uz

Submission #982028

# Submission time Handle Problem Language Result Execution time Memory
982028 2024-05-13T18:12:27 Z FZ_Melo Sequence (APIO23_sequence) C++17
0 / 100
 39 ms 9096 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Incorrect 1 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Incorrect 1 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Runtime error 38 ms 9060 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Runtime error 35 ms 9044 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 9096 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Incorrect 1 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Incorrect 1 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -