Submission #984453

#	Time	Username	Problem	Language	Result	Execution time	Memory
984453		IUA_Hasin	Sequence (APIO23_sequence)	C++17	7 / 100	138 ms	39188 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

#define ll                                long long

using namespace std;

const ll M = 5e5+10;

ll freq[M];
ll leftfreq[M];
ll rightfreq[M];

int sequence(int N, std::vector<int> A) {
      ll ans = 1;
      ll xind = -1;
      for(int i=0; i<N; i++){
        freq[A[i]]++;
      }
      for(int i=1; i<N; i++){
        if(A[i-1]>A[i]){
          xind = i-1;
          break;
        }
      }
      if(xind==-1){
        xind = N-1;
      }

      if(xind!=0 && xind!=N-1){
        map<ll, ll> m;
        for(int i=xind; i<N; i++){
          m[A[i]] = i;
        }

        for(int i=0; i<xind; i++){
          ll a = A[i];
          ll b = m[a];
          if(b>0){
            ll total = b-i+1;
            ll left = i;
            ll right = N-1-b;
            ll tempfreq = freq[a];
            ll big = total-tempfreq;
            if(big%2==0){
              if(left+right>=big){
                ans = max(ans, tempfreq);
              }
            } else {
              if(left+right>=big-1){
                ans = max(ans, tempfreq);
              }
            }
          }
        }
        
        for(int i=0; i<=xind; i++){
          leftfreq[A[i]]++;
          ans = max(ans, leftfreq[A[i]]);
        }

        for(int i=xind+1; i<N; i++){
          rightfreq[A[i]]++;
          ans = max(ans, rightfreq[A[i]]);
        }
        
        return ans;
      } else {
        for(int i=0; i<N; i++){
          leftfreq[A[i]]++;
          ans = max(ans, leftfreq[A[i]]);
        }
        return ans;
      }

      //return ans;

}

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