Submission #981961

#	Time	Username	Problem	Language	Result	Execution time	Memory
981961		vjudge1	Sequence (APIO23_sequence)	C++17	100 / 100	945 ms	57940 KiB

sequence

// hola soy Dember :D
// 31/03/2024

#include <bits/stdc++.h>

#define ll int
#define pll pair<ll,ll>
#define F first
#define S second 
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z

using namespace std;
const int MN=5e5+5;
 
vector<ll> v[MN];
ll L[MN], R[MN];
ll minx[4*MN], maxx[4*MN], lazy[4*MN];
ll a[MN], b[MN], ans=1;

void push(ll i, ll l, ll r){
    if(!lazy[i])return;
    minx[i]+=lazy[i];
    maxx[i]+=lazy[i];
    if(l!=r){
        lazy[i*2]+=lazy[i];
        lazy[i*2+1]+=lazy[i];
    }
    lazy[i]=0;
    return;
}//
 
void bld(ll i, ll l, ll r, ll xd, ll zd, ll p){
    push(i, l, r);
    if(l>zd || r<xd)return;
    if (xd<=l && r<=zd) {
        lazy[i]=p;
        push(i, l, r);
        return;
    }
    
    bld(2*i, l, (l+r)/2, xd, zd, p);
    bld(2*i+1, (l+r)/2+1, r, xd, zd, p);
    
    minx[i]=min(minx[2*i], minx[2*i+1]);
    maxx[i]=max(maxx[2*i], maxx[2*i+1]);
    return;
}//
 
ll qmin(ll i, ll l, ll r, ll xd, ll zd){
    push(i, l, r);
    if(l>zd || r<xd)return 1e9;
    if(xd<=l && r<=zd)return minx[i];
    
    return min(qmin(2*i, l, (l+r)/2, xd, zd), qmin(2*i+1, (l+r)/2+1, r, xd, zd));
}//
ll qmax(ll i, ll l, ll r, ll xd, ll zd) {
    push(i, l, r);
    if(l>zd || r<xd)return -1e9;
    if(xd<=l && r<=zd)return maxx[i];
    
    return max(qmax(2*i, l, (l+r)/2, xd, zd), qmax(2*i+1, (l+r)/2+1, r, xd, zd));
}//
ll res;
void BB(ll l, ll r, ll zd, ll p){
    if(l>r)return;
    
    if (zd+(p+1)*2>=a[(l+r)/2]) {
        res=(l+r)/2;
        BB(l,(l+r)/2-1,zd,p);
        return;
    } 
    BB((l+r)/2+1, r,zd,p);
    return;
}
 
int sequence(int n, vector<int> A) {
    fo(i,1,n)v[A[i-1]].push_back(i),bld(1, 0, n, i, i, -i);
 
    fo(h,1,n){
        ll j=0, k=0, ola=v[h].Z;
        a[0]=1e9;
        fo(i,0,ola-1){
            ll x=v[h][i];
            L[i]=qmin(1, 0, n, 0, x-1);
            R[i]=qmax(1, 0, n, 0, x-1);
            
            ll xd= qmin(1, 0, n, x, n);
            ll zd= qmax(1, 0, n, x, n);
            
            while(j<=i && L[j]>zd || R[j]<xd) {
                if (L[j]+j*2<=a[k]) {
                    k++;
                    a[k]=L[j]+j*2;
                    b[k]=j;
                }
                j++;
            }
            
            if(j>0 && L[j-1]>zd){
                res=0;
                BB(1,k,zd,i);
                if(res)ans=max(ans, i-b[res]+1);
            }
            
            ans=max(ans, i-j+1);
        }
        for(auto u:v[h])bld(1, 0, n, u, n, 2);
    }
    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:96:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   96 |             while(j<=i && L[j]>zd || R[j]<xd) {
      |                   ~~~~~^~~~~~~~~~

• 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