Submission #955113

#	Time	Username	Problem	Language	Result	Execution time	Memory
955113		Otalp	Sequence (APIO23_sequence)	C++17	100 / 100	1719 ms	672268 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

int a[500100], b[500100];
int s1[500100], s2[500100], c[500100];
struct node{
    pii x={1e9, -1e9};
    node *l = nullptr, *r = nullptr;
    node(){}
};
 
 
 
void upd(node *v, int l, int r, int pos, int x){
    if(l == r){
        v -> x = {min(v -> x.ff, x), max(v -> x.ss, x)};
        return;
    }
    int mid = floor(((double)l + (double)r) / 2);
    if(mid >= pos){
        if(!v -> l) v->l = new node();
        upd(v -> l, l, mid, pos, x);
    }
    else{
        if(!v -> r) v->r = new node();
        upd(v->r, mid+1, r, pos, x);
    }
    v -> x = {1e9, -1e9};
    if(v -> l) v -> x = {min(v -> x.ff, v -> l -> x.ff), max(v -> x.ss, v -> l -> x.ss)};
    if(v -> r) v -> x = {min(v -> x.ff, v -> r -> x.ff), max(v -> x.ss, v -> r -> x.ss)};
}
 
pii get(node *v, int l, int r, int L, int R){
    if(r < L or R < l){
        return {1e9, -1e9};
    }
    if(L <= l and r <= R){
        return v -> x;
    }
    int mid=floor(((double)l + (double)r) / 2);
    pii x = {1e9, -1e9};
    if(v -> l){
        pii k = get(v -> l, l, mid, L, R);
        x = {min(x.ff, k.ff), max(x.ss, k.ss)};
    }

    if(v -> r){
        pii k = get(v -> r, mid + 1, r, L, R);
        x = {min(x.ff, k.ff), max(x.ss, k.ss)};
    }
    return x;
}

pii t[2000100];
int p[2001000];

void push(int v){
    if(!p[v]) return;
    t[v+v].ff += p[v];
    t[v+v+1].ff += p[v];
    t[v+v].ss += p[v];
    t[v+v+1].ss += p[v];

    p[v+v] += p[v];
    p[v+v+1] += p[v];

    p[v] = 0;
}


void updq(int v, int l, int r, int L, int R, int x){
    if(r < L or R < l){
        return;
    }
    if(L <= l and r <= R){
        t[v].ff += x;
        t[v].ss += x;
        p[v] += x;
        return;
    }
    int mid=(l+r)/2;
    push(v);
    updq(v+v, l, mid, L, R, x);
    updq(v+v+1, mid+1, r, L, R, x);
    t[v] = {min(t[v+v].ff, t[v+v+1].ff), max(t[v+v].ss, t[v+v+1].ss)};
}

pii getq(int v, int l, int r, int L, int R){
    if(r < L or R < l){
        return {1e9, -1e9};
    }
    if(L <= l and r <= R){
        return t[v];
    }
    int mid=(l+r)/2;
    push(v);
    pii k1=getq(v+v, l, mid, L, R), k2=getq(v+v+1, mid+1, r, L, R);
    return {min(k1.ff, k2.ff), max(k1.ss, k2.ss)};
}

vector<int> pos[500100];

int sequence(int n, vector<int> A) {
    int ans = 0;
    for(int i=1; i<=n; i++){
        a[i] = A[i - 1];
        pos[a[i]].pb(i);
    }
    for(int i=1; i<=n; i++){
        b[i] = 1;
        updq(1, 0, n, i, n, 1);
    }
    for(int x=1; x<=n; x++){
        if(pos[x].size() == 0) continue;
        int ls = 0;
        vector<pii> q;
        for(int i=0; i<pos[x].size(); i++){
            updq(1, 0, n, pos[x][i], n, -b[pos[x][i]]);
            b[pos[x][i]] = 0;
            q.pb(getq(1, 0, n, ls, pos[x][i]));
            ls = pos[x][i];
        }

        q.pb(getq(1, 0, n, ls, n));
        vector<pair<pii, int> > zap;
        for(int i=0; i<q.size(); i++){
            zap.pb({{q[i].ss + i, q[i].ff-i}, i});
        }
        vector<pair<pii, int> > h;
        for(int i=0; i<q.size(); i++){
            h.pb({{q[i].ff+i, q[i].ss-i}, i});
        }
        sort(h.begin(), h.end());
        sort(zap.begin(), zap.end());
        ls = 0;
        node *t = new node();
        int d = n + 1;
        for(int i=0; i<zap.size(); i++){
            int L=zap[i].ff.ff, R=zap[i].ff.ss;
            while(ls < h.size() and h[ls].ff.ff <= L){
                upd(t, d - n, d + n, h[ls].ff.ss + d, h[ls].ss);
                ls++;
            }
            pii dd = get(t, d-n, d+n, d+R, d+n);
            ans = max(ans, max(zap[i].ss - dd.ff, dd.ss - zap[i].ss));
        }
        for(int i: pos[x]){
            updq(1, 0, n, i, n, -1);
            b[i] = -1;
        }
    }
    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int i=0; i<pos[x].size(); i++){
      |                      ~^~~~~~~~~~~~~~
sequence.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int i=0; i<q.size(); i++){
      |                      ~^~~~~~~~~
sequence.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int i=0; i<q.size(); i++){
      |                      ~^~~~~~~~~
sequence.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         for(int i=0; i<zap.size(); i++){
      |                      ~^~~~~~~~~~~
sequence.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |             while(ls < h.size() and h[ls].ff.ff <= L){
      |                   ~~~^~~~~~~~~~

• 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