Submission #852249

#	Time	Username	Problem	Language	Result	Execution time	Memory
852249		sunwukong123	Sequence (APIO23_sequence)	C++17	100 / 100	1234 ms	91812 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 500005;

const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
int A[MAXN];
vector<int> V[MAXN];
struct node {
    int s,e,m,lazy,mn,mx;
    node *l, *r;
    node (int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        lazy=0;
        
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
            mn=min(l->mn,r->mn);
            mx=max(l->mx,r->mx);
        } else{
            mn=-_s;mx=-_s;
        }
    }

    void value(){
        if(lazy==0)return;
        if(s==e){
            mn+=lazy;
            mx+=lazy;
            lazy=0;
            return;
        }
        l->lazy+=lazy;
        r->lazy+=lazy;
        mn+=lazy;
        mx+=lazy;
        lazy=0;
        return;
    }
    void update(int x, int y, int nval){
        value();
        if(s==x&&e==y){
            lazy+=nval;
            return;
        }
        if(x>m)r->update(x,y,nval);
        else if(y<=m)l->update(x,y,nval);
        else l->update(x,m,nval),r->update(m+1,y,nval);
        l->value();r->value();
        mn=min(l->mn,r->mn);
        mx=max(l->mx,r->mx);
    }
    int query_min(int x, int y){
        value();
        if(s==x&&e==y)return mn;
        if(x>m)return r->query_min(x,y);
        else if(y<=m)return l->query_min(x,y);
        else return min(l->query_min(x,m),r->query_min(m+1,y));
    }
    int query_max(int x, int y){
        value();
        if(s==x&&e==y)return mx;
        if(x>m)return r->query_max(x,y);
        else if(y<=m)return l->query_max(x,y);
        else return max(l->query_max(x,m),r->query_max(m+1,y));
    }
    ~node(){
        if(s!=e){
            delete l;
            delete r;
        }
        
    }
}*seg;
int Q1[MAXN],Q2[MAXN],Q3[MAXN],Q4[MAXN];
bool check(int S){
    for(int v=1;v<=n;v++){

        //pretend everything 0 is a -1
        vector<int> idxes;
        for(int i=0;i+S-1<(int)V[v].size();i++){
            int st=V[v][i];
            int en=V[v][i+S-1];

            int Lval=Q1[st];//seg->query_max(0,st-1);
            int Rval=Q2[en];//seg->query_min(en,n);

            if(Rval<=Lval){
                idxes.push_back(i);
            }
        }

        // pretend every 0 is a +1

        for(auto i:idxes){
            int st=V[v][i];
            int en=V[v][i+S-1];
            int Lval=Q3[st];//seg->query_min(0,st-1);
            int Rval=Q4[en];//seg->query_max(en,n);

            if(Rval>=Lval){

                return 1;
            }
        }

    }
   // delete seg;
    return 0;
}

int sequence(int N, std::vector<int> vec) {
    n=N;
    for(int i=1;i<=n;i++){
        A[i]=vec[i-1];
    }
    for(int i=1;i<=n;i++){
        V[A[i]].push_back(i);
    }

    seg=new node(0,n);
    for(int v=1;v<=n;v++){
        //pretend everything 0 is a -1
        vector<int> idxes;
        for(int i=0;i<(int)V[v].size();i++){
            int idx=V[v][i];
            Q1[idx]=seg->query_max(0,idx-1);
            Q2[idx]=seg->query_min(idx,n);
        }

        for(auto x:V[v]){
            seg->update(x,n,2);
        }

        // pretend every 0 is a +1

        for(int i=0;i<(int)V[v].size();i++){
            int idx=V[v][i];
            Q3[idx]=seg->query_min(0,idx-1);
            Q4[idx]=seg->query_max(idx,n);
        }
    }

    int lo=0,hi=n+1;
    while(lo<hi-1){
        int mid=(lo+hi)/2;
        if(check(mid))lo=mid;
        else hi=mid;
    }
    return lo;
}

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