Submission #770164

#	Time	Username	Problem	Language	Result	Execution time	Memory
770164		gg123_pe	Sequence (APIO23_sequence)	C++17	63 / 100	2072 ms	71284 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 ST{  
    ii st[4*N], zero = {inf, -inf}; 
    int lazy[4*N]; 

    ii merge(ii a, ii b){
        return {min(a.first, b.first), max(a.second, b.second)}; 
    }
    void down(int id){
        lazy[id<<1] += lazy[id], lazy[id<<1|1] += lazy[id]; 
        st[id<<1].first += lazy[id], st[id<<1].second += lazy[id]; 
        st[id<<1|1].first += lazy[id], st[id<<1|1].second += lazy[id]; 
        lazy[id] = 0; 
    }
    void Upd(int id, int l, int r, int x, int y, int val){
        if(r < x or y < l) return; 
        if(x <= l and r <= y){
            lazy[id] += val; 
            st[id].first += val, st[id].second += 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]); 
    }
    ii 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)); 
    }
    int val(int pos){
        if(pos == 0) return 0; 
        return query(1, 1, n, pos, pos).first; 
    }
    void upd(int node, int val){
        Upd(1, 1, n, node, n, val); 
    }
}st[2]; 

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

    if(x != 1){
        ii C1 = st[0].query(1, 1, n, 1, x-1); 
        ii C2 = st[1].query(1, 1, n, 1, x-1); 

        maL = max(0, max(VL1, VL1 - C1.first)); 
        miL = min(0, min(VL2, VL2 - C2.second)); 
    }
    if(y != n){
        ii C1 = st[0].query(1, 1, n, y+1, n); 
        ii C2 = st[1].query(1, 1, n, y+1, n); 

        maR = max(0, C1.second - VR1);  
        miR = min(0, C2.first - 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[0].upd(i, 1); 
        st[1].upd(i, 1); 
    }

    int ans = 1; 
    f(i,1,n+1){
        int len = pos[i].size(); 
        for(int x: pos[i]){
            st[1].upd(x, -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[0].upd(x, -2); 
        }
    }
    return ans; 
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 0 / 18