Submission #1031666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031666		vjudge1	Sequence (APIO23_sequence)	C++17	35 / 100	605 ms	33360 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>stt;
map<int,int>mp;
int sequence(int N, std::vector<int> A) {
    int ans=0;
    vector<int>A2=A;
    if(N<3000){
        for(int i=0;i<N;i++){
            mp.clear();
            stt.clear();
            for(int j=i;j<N;j++){
                stt.insert(A[j]);
                mp[A[j]]++;
                int a=*stt.find_by_order((j-i)/2),b=*stt.find_by_order((j-i+1)/2);
                ans=max({ans,mp[a],mp[b]});
            }
        }
        return ans;
    }
    int dec1=N,dec2=0;
    for(int i=1;i<N;i++){
        if(A[i]<A[i-1]){
            dec1=i;
            break;
        }
    }
    for(int i=N;i--;){
        if(A[i]>A[i-1]){
            dec2=i;
            break;
        }
    }
    if(dec1>dec2) {
        sort(A2.begin(),A2.end());
        int C=A2[N-1>>1];
        map<int,int>mp1,mp2;
        for(int i=0;i<dec1;i++)
            mp1[A[i]]++;
        for(int i=dec1;i<N;i++)
            mp2[A[i]]++;
        for(auto [i,j]:mp1)
            ans=max(ans,j);
        for(auto [i,j]:mp2)
            ans=max(ans,j);
        for(int i=0;i<N;i++) if(A[i]>=C)
            ans=max(ans,mp1[A[i]]+mp2[A[i]]);
        return ans;
    }
    return 1;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:40:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   40 |         int C=A2[N-1>>1];
      |                  ~^~

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