제출 #1283307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283307		StefanSebez	서열 (APIO23_sequence)	C++20	100 / 100	1659 ms	77668 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=5e5+50,inf=1e9;
int n;vector<int>a;
struct Node{int mn,maks;};
Node Merge(Node a,Node b){return {min(a.mn,b.mn),max(a.maks,b.maks)};}
struct SegTree{
    int root,nc,lc[2*N],rc[2*N],lazy[2*N];Node node[2*N];
    void update(int &c,int x){if(!c)c=++nc;node[c].mn+=x;node[c].maks+=x;lazy[c]+=x;}
    void push(int &c){if(!c)c=++nc;update(lc[c],lazy[c]);update(rc[c],lazy[c]);lazy[c]=0;}
    void Update(int &c,int ss,int se,int qs,int qe,int x){
        if(!c)c=++nc;
        if(qs>qe||qe<ss||se<qs)return;
        if(qs<=ss&&se<=qe){update(c,x);return;}
        int mid=ss+se>>1;push(c);
        if(qe<mid+1) Update(lc[c],ss,mid,qs,qe,x);
        else if(mid<qs) Update(rc[c],mid+1,se,qs,qe,x);
        else Update(lc[c],ss,mid,qs,qe,x),Update(rc[c],mid+1,se,qs,qe,x);
        node[c]=Merge(node[lc[c]],node[rc[c]]);
    }
    void Update(int i,int x){Update(root,0,n,i,n,x);}
    Node Get(int &c,int ss,int se,int qs,int qe){
        if(!c)c=++nc;
        if(qs>qe||qe<ss||se<qs)return {inf,-inf};
        if(qs<=ss&&se<=qe) return node[c];
        int mid=ss+se>>1;push(c);
        if(qe<mid+1) return Get(lc[c],ss,mid,qs,qe);
        else if(mid<qs) return Get(rc[c],mid+1,se,qs,qe);
        return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST,ST1;
vector<int>ind[N];
bool Check(int x,int i,int j){
    Node y=ST.Get(ST.root,0,n,0,ind[x][i]-1),z=ST.Get(ST.root,0,n,ind[x][j],n);
    int v1=z.maks-y.mn;
    y=ST1.Get(ST1.root,0,n,0,ind[x][i]-1),z=ST1.Get(ST1.root,0,n,ind[x][j],n);
    int v2=z.mn-y.maks;
    if((v1>=0&&v2<=0)||(v1<=0&&v2>=0)) return true;
    return false;
}
int sequence(int n1,vector<int>A){
    n=n1;a={0};for(auto i:A) a.pb(i);
    for(int i=1;i<=n;i++) ind[i].pb(0);
    for(int i=1;i<=n;i++) ind[a[i]].pb(i);
    for(int i=1;i<=n;i++) ind[i].pb(n+1);
    int res=1;
    for(int i=1;i<=n;i++) ST.Update(i,1),ST1.Update(i,1);
    for(int x=1;x<=n;x++){
        for(int i=1;i+1<ind[x].size();i++) ST1.Update(ind[x][i],-2);
        for(int i=1,j=i;i+1<ind[x].size();i++){
            while(j+1<ind[x].size()&&Check(x,i,j)) j++;
            res=max(res,j-i);
        }
        for(int i=1;i+1<ind[x].size();i++) ST.Update(ind[x][i],-2);
    }
    return res;
}

• 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