Submission #1031643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031643		vjudge1	Sequence (APIO23_sequence)	C++17	35 / 100	610 ms	44624 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<=2000){
        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;
    }
    sort(A2.begin(),A2.end());
    int dec=N;
    int C=A2[N-1>>1];
    for(int i=1;i<N;i++){
        if(A[i]<A[i-1]){
            dec=i;
            break;
        }
    }
    map<int,int>mp1,mp2;
    for(int i=0;i<dec;i++)
        mp1[A[i]]++;
    for(int i=dec;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;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:27:15: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   27 |     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