Submission #749197

#	Time	Username	Problem	Language	Result	Execution time	Memory
749197		beepbeepsheep	Sequence (APIO23_sequence)	C++17	100 / 100	1448 ms	125516 KiB

sequence

#include "sequence.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>

const ll maxn=5e5+5;
ll pref[maxn][2];
ll suff[maxn][2];
vector<int> adj[maxn];
struct node{
    ll s,e,m,mn,mx,flag;
    node *l,*r;
    node(ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,mn=0,mx=0,flag=0;
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void prop(){
        if (!flag) return;
        mn+=flag;
        mx+=flag;
        if (s==e){
            flag=0;
            return;
        }
        l->flag+=flag;
        r->flag+=flag;
        flag=0;
        return;
    }
    void upd(ll x, ll y, ll v){
        if (x<=s && e<=y){
            flag+=v;
            return;
        }
        if (x>m) r->upd(x,y,v);
        else if (y<=m) l->upd(x,y,v);
        else l->upd(x,y,v),r->upd(x,y,v);
        l->prop(),r->prop();
        mn=min(l->mn,r->mn);
        mx=max(l->mx,r->mx);
    }
    ll queryMin(ll x, ll y){
        prop();
        if (x<=s && e<=y) return mn;
        if (x>m) return r->queryMin(x,y);
        if (y<=m) return l->queryMin(x,y);
        return min(l->queryMin(x,y),r->queryMin(x,y));
    }
    ll queryMax(ll x, ll y){
        prop();
        if (x<=s && e<=y) return mx;
        if (x>m) return r->queryMax(x,y);
        if (y<=m) return l->queryMax(x,y);
        return max(l->queryMax(x,y),r->queryMax(x,y));
    }
}*root;
ll n;
bool check(ll m){
    for (int i=1;i<=n;i++){
        for (int j=0;j+m<=adj[i].size();j++){
            ll A=pref[adj[i][j]][0];
            ll B=pref[adj[i][j]][1];
            ll C=suff[adj[i][j+m-1]][0];
            ll D=suff[adj[i][j+m-1]][1];
            if (max(A,C)-m<= min(B,D)) return true;
        }
    }
    return false;
}
int sequence(int N, std::vector<int> A) {
    n=N;
    for (int i=0;i<N;i++){
        adj[A[i]].emplace_back(i+1);
    }
    root=new node(0,N);
    for (int i=1;i<=N;i++){
        root->upd(i,N,1);
    }
    for (int i=1;i<=N;i++){
        for (auto u:adj[i]){
            root->upd(u,N,-1);
        }
        for (int j=0;j<adj[i].size();j++){
            ll u=adj[i][j];
            pref[u][0]=root->queryMin(0,u-1);
            pref[u][1]=root->queryMax(0,u-1);
            if (j!=0){
                pref[u][0]=min(pref[u][0],pref[adj[i][j-1]][0]-1);
                pref[u][1]=max(pref[u][1],pref[adj[i][j-1]][1]+1);
            }

        }
        for (int j=adj[i].size()-1;j>=0;j--){
            ll u=adj[i][j];
            suff[u][0]=root->queryMin(u,N);
            suff[u][1]=root->queryMax(u,N);
            if (j!=adj[i].size()-1){
                suff[u][0]=min(suff[u][0],suff[adj[i][j+1]][0]-1);
                suff[u][1]=max(suff[u][1],suff[adj[i][j+1]][1]+1);
            }
        }
        for (auto u:adj[i]){
            root->upd(u,N,-1);
        }
    }
    ll l=1,r=N+1,m;
    while (l!=r-1){
        m=(l+r)>>1;
        if (check(m)) l=m;
        else r=m;
    }
    return l;
}

Compilation message (stderr)

sequence.cpp: In function 'bool check(long long int)':
sequence.cpp:66:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j=0;j+m<=adj[i].size();j++){
      |                      ~~~^~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int j=0;j<adj[i].size();j++){
      |                      ~^~~~~~~~~~~~~~
sequence.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             if (j!=adj[i].size()-1){
      |                 ~^~~~~~~~~~~~~~~~~

• 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