Submission #1031673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031673		vjudge1	Sequence (APIO23_sequence)	C++17	35 / 100	609 ms	77704 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
struct segtree{
    struct info{
        int mxprf=0;
        int mnprf=0;
        int mxsuf=0;
        int mnsuf=0;
        int sum=0;
        info(){}
        info(int k){
            if(k>0)mxprf=mxsuf=sum=0;
            else mnprf=mnsuf=sum=k;
        }
        info(info a,info b){
            sum=a.sum+b.sum;
            mxprf=max(a.mxprf,b.mxprf+a.sum);
            mnprf=min(a.mnprf,b.mnprf+a.sum);
            mxsuf=max(b.mxsuf,a.mxsuf+b.sum);
            mnsuf=min(b.mnsuf,a.mnsuf+b.sum);
        }
    } T[1<<20];
    void upd(int i,int l,int r,int p,int x){
        if(l==r)return void(T[i]=info(x));
        if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
        else upd(i*2,l,l+r>>1,p,x);
        T[i]=info(T[i*2],T[i*2+1]);
    }
    info qry(int i,int l,int r,int ll,int rr){
        if(ll>r||l>rr)return info();
        if(ll<=l&&r<=rr) return T[i];
        return info(qry(i*2,l,l+r>>1,ll,rr),
                qry(i*2+1,l+r+2>>1,r,ll,rr));
    }
} TRE;
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=1;
    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;
    }
    map<int,int>mp;
    for(auto i:A)mp[i];
    int CC=0;
    for(auto&[i,j]:mp)
        j=++CC;
    vector<int>v[500100];
    for(auto&i:A)
        i=mp[i];
    for(int i=0;i<N;i++)
        v[A[i]].push_back(i+1);
    for(int i=1;i<=N;i++)
        TRE.upd(1,1,N,i,1);
    for(int i=1;i<=CC;i++){
        for(auto k:v[i])
            TRE.upd(1,1,N,k,0);
        if(v[i].size()==2){
            int x=TRE.qry(1,1,N,v[i][0],v[i][1]).sum;
            if(x>0){
                x+=TRE.qry(1,1,N,1,v[i][0]-1).mnsuf;
                x+=TRE.qry(1,1,N,v[i][1]+1,N).mnprf;
            } else {
                x+=TRE.qry(1,1,N,1,v[i][0]-1).mxsuf;
                x+=TRE.qry(1,1,N,v[i][1]+1,N).mxprf;
            }
            if(abs(x)<3) return 2;
        }
        for(auto k:v[i])
            TRE.upd(1,1,N,k,-1);
    }
    return 1;
}

Compilation message (stderr)

sequence.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
sequence.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
      |            ~^~
sequence.cpp:28:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
      |                                ~~~^~
sequence.cpp:29:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         else upd(i*2,l,l+r>>1,p,x);
      |                        ~^~
sequence.cpp: In member function 'segtree::info segtree::qry(int, int, int, int, int)':
sequence.cpp:35:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         return info(qry(i*2,l,l+r>>1,ll,rr),
      |                               ~^~
sequence.cpp:36:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |                 qry(i*2+1,l+r+2>>1,r,ll,rr));
      |                           ~~~^~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:73:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   73 |         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