Submission #770173

#	Time	Username	Problem	Language	Result	Execution time	Memory
770173		gg123_pe	Sequence (APIO23_sequence)	C++17	100 / 100	1363 ms	56320 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h> 
using namespace std;

typedef pair<int,int> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 5e5 + 5; 
const int inf = 2e9; 

int n; 
vector <int> pos[N]; 

struct t{
    int m1 = 0, M1 = 0, m2 = 0, M2 = 0; 
}zero = {inf, -inf, inf, -inf}; 

struct ST{  
    t st[4*N]; 
   
    ii lazy[4*N], Zero; 

    t merge(t a, t b){
        return {min(a.m1, b.m1), max(a.M1, b.M1), min(a.m2, b.m2), max(a.M2, b.M2)}; 
    }
    void UPD(int id, ii a){
        st[id].m1 += a.first, st[id].M1 += a.first, st[id].m2 += a.second, st[id].M2 += a.second; 
        lazy[id].first += a.first; 
        lazy[id].second += a.second; 
    }
    void down(int id){
        if(lazy[id].first != 0 or lazy[id].second != 0){
            UPD(id<<1, lazy[id]), UPD(id<<1|1, lazy[id]); 
            lazy[id] = Zero;  
        }
    }
    void Upd(int id, int l, int r, int x, int y, ii val){
        if(r < x or y < l) return; 
        if(x <= l and r <= y){
            UPD(id, val); 
            return; 
        }
        down(id); 
        int m = (l+r)>>1; 
        Upd(id<<1, l, m, x, y, val), Upd(id<<1|1, m+1, r, x, y, val); 
        st[id] = merge(st[id<<1], st[id<<1|1]); 
    }
    t query(int id, int l, int r, int x, int y){
        if(r < x or y < l) return zero; 
        if(x <= l and r <= y) return st[id]; 
        down(id); 
        int m = (l+r)>>1; 
        return merge(query(id<<1, l, m, x, y), query(id<<1|1, m+1, r, x, y)); 
    }
    ii val(int pos){
        if(pos == 0) return Zero; 
        t C = query(1, 1, n, pos, pos); 
        return {C.m1, C.m2}; 
    }
    void upd(int node, ii val){
        Upd(1, 1, n, node, n, val); 
    }
}st; 

int sign(int x){
    if(x == 0) return x; 
    return x / abs(x); 
}
bool check(int x, int y){
    ii R1 = st.val(x-1), R2 = st.val(y); 
    int VL1 = R1.first, VR1 = R2.first, sum1 = VR1 - VL1; 
    int VL2 = R1.second, VR2 = R2.second, sum2 = VR2 - VL2; 
    int maL = 0, maR = 0; 
    int miL = 0, miR = 0; 

    if(x != 1){
        t C = st.query(1, 1, n, 1, x-1); 
    
        maL = max(0, max(VL1, VL1 - C.m1)); 
        miL = min(0, min(VL2, VL2 - C.M2)); 
    }
    if(y != n){
        t C = st.query(1, 1, n, y+1, n); 
    
        maR = max(0, C.M1 - VR1);  
        miR = min(0, C.m2 - VR2); 
    }
    return sign(sum1 + maL + maR) * sign (sum2 + miL + miR) <= 0; 
}
int sequence(int Ni, vector<int> A) {
    n = Ni; 
    f(i,0,n){
        pos[A[i]].push_back(i+1); 
    }

    f(i,1,n+1){
        st.upd(i, {1, 1});
    }

    int ans = 1; 
    f(i,1,n+1){
        int len = pos[i].size(); 
        for(int x: pos[i]){
            st.upd(x, {0, -2}); 
        }
        int r = -1; 
        f(j,0,len){
            r = max(r, j); 
            while(r < len and check(pos[i][j], pos[i][r])) r++;
            r--; 
            ans = max(ans, r - j + 1);  
        }
        for(int x: pos[i]){
            st.upd(x, {-2, 0}); 
        }
    }
    return ans; 
}

• 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