Submission #769623

#	Time	Username	Problem	Language	Result	Execution time	Memory
769623		gg123_pe	Sequence (APIO23_sequence)	C++17	47 / 100	301 ms	45416 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 = 1e9; 

int n; 
int bit[N], c[N];
vector <pair<int,int>> pos[N]; 

void upd(int x, int val){
    for(; x < N; x = (x|(x+1))) bit[x] += val; 
}
int sum(int x){
    int res = 0;
    for(; x >= 0; x = (x&(x+1)) - 1) res += bit[x];  
    return res; 
}
int get(int x){
    int l = 1, r = n; 
    while(l < r){
        int m = (l+r)>>1; 
        if(sum(m) >= x) r = m; 
        else l = m+1; 
    }
    return c[l]; 
}
int subtask_2(vector <int> A){
    int ans = 1; 
    f(i,0,n){
        c[A[i]]++; 
        upd(A[i], 1); 

        f(j,i,n){
            int l = j - i + 1; 
            if(l&1){
                ans = max(ans, get((l+1)/2)); 
            }
            else{
                ans = max(ans, get(l/2)); 
                ans = max(ans, get(l/2 + 1)); 
            }
            if(j+1 < n) {
                c[A[j+1]]++; 
                upd(A[j+1], 1); 
            }
        }
        f(j,i,n){
            c[A[j]]--; 
            upd(A[j], -1); 
        }
    }
    return ans;
}
int id(int pos){
    if(pos == 0) return 0; 
    if(c[1] >= pos) return 1; 
    if(c[1] + c[2] >= pos) return 2; 
    return 3; 
}
int res(vector <int> v){
    vector <int> aux, mini; 
    int len = v.size(), ans = 1; 
    f(i,0,len) {
        aux.push_back(v[i] - 2*i); 
        mini.push_back(v[i] - 2*i); 
    }
    fa(i,len-2,0) mini[i] = min(mini[i+1], mini[i]); 

    f(i,0,len-1){
        int ult = aux[i] + 1; // <= ult
        if(mini[i+1] > ult) continue; 
        int l = i+1, r = len-1; 
        while(l < r){
            int m = (l+r+1)>>1; 
            if(mini[m] > ult) r = m-1;  
            else l = m; 
        }
        ans = max(ans, l-i+1); 
    }
    return ans;     
}
int subtask_4(vector <int> A){
    for(int x: A) c[x]++; 
    int p1 = 0, p2 = 0; 
    if(n&1) p1 = (n+1)/2; 
    else p1 = n/2, p2 = p1 + 1; 

    if(id(p1) == 1 or id(p1) == 3) return c[id(p1)]; 
    if(id(p2) == 1 or id(p2) == 3) return c[id(p2)]; 
    if(c[2] > c[1] and c[2] > c[3]) return c[2]; 

    int ans = c[2];
    vector <int> P1, P3; 
    f(i,0,n){
        if(A[i] == 1) P1.push_back(i); 
        if(A[i] == 3) P3.push_back(i); 
    }
    ans = max(ans, res(P1)); 
    ans = max(ans, res(P3)); 
    return ans; 
}
bool is(int l, int r, int ty){
    if(l > r) return 0; 
    if(l != r) return 1; 
    return l%2 == ty; 
}
int subtask_3(vector <int> A){
    int ans = 0, id = 0; 
    while(id < n){
        int c = 0, ini = id+1, comp = A[id]; 
        while(A[id] == comp and id < n) c++, id++; 
        ans = max(ans, c);  
        pos[comp].push_back({ini, ini + c - 1}); 
    } 
    f(i,1,n+1){
        if(pos[i].size() != 2) continue; 
        int l1 = pos[i][0].first, r1 = pos[i][0].second; 
        int l2 = pos[i][1].first, r2 = pos[i][1].second; 
        int C = r1 - l1 + r2 - l2 + 2;
        int B = -(r1 + 1) + (l2 - 1) + 1;
        int A = n - C - B, ty = (B+C)%2; 

        bool fe = 0; 
        if(is(max(0, B-C), min(A, B+C), ty)) fe = 1; 
        if(is(max(0, B-C-1), min(A, B+C-1), 1-ty)) fe = 1; 
        if(fe) ans = max(ans, C);    
    }
    return ans; 
}



struct ST{
    int lazy[4*N]; 
    ii st[4*N];  // min, max
    ii zero = {inf, -inf}; 

    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; 
    }
    ii merge(ii x, ii y){
        return {min(x.first, y.first), max(x.second, y.second)}; 
    }
    void upd(int id, int l, int r, int x, int y, int val){ // [x, y] += 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, 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){
        return query(1, 1, n, pos, pos).first; 
    }
}st; 

ii p[N]; 
int a[N]; 

int subtask_5(vector <int> A){
    f(i,1,n+1){
        int x = A[i-1]; 
        if(p[x].first == 0) p[x].first = i; 
        else p[x].second = i; 
    }

    st.upd(1, 1, n, 1, n, 1); 
    f(i,1,n+1) a[i] = 1; 

    f(i,1,n+1){
        int x = p[i].first, y = p[i].second; 
        if(y == 0){
            if(x != 0) st.upd(1, 1, n, x, n, -1-a[x]), a[x] = -1; 
            continue; 
        }
        st.upd(1, 1, n, x, n, -a[x]), a[x] = 0; 
        st.upd(1, 1, n, y, n, -a[y]), a[y] = 0; 

        // check
        int SL = 0, _SR = st.val(y); 
        if(x != 1) SL = st.val(x-1); 
        
        int sum = _SR - SL; 
        int miL = 0, maL = 0; 
        int miR = 0, maR = 0; 
        if(x != 1){
            ii C = st.query(1, 1, n, 1, x-1); 
            miL = min(0, SL - C.second); 
            maL = max(0, SL - C.first); 
        }
        if(y != n){
            ii C = st.query(1, 1, n, y+1, n); 
            miR = min(0, C.first - _SR); 
            maR = max(0, C.second - _SR); 
        }
    
        int mi = miL + miR + sum; 
        int ma = maL + maR + sum; 
        
        if(min(2, ma) - max(-2, mi) + 1 > 0) return 2; 
        st.upd(1, 1, n, x, n, -1-a[x]), a[x] = -1; 
        st.upd(1, 1, n, y, n, -1-a[y]), a[y] = -1; 
    }
    return 1; 
}
int sequence(int Ni, vector<int> A) {
    n = Ni; 

    if(n <= 2000) return subtask_2(A); 
    
    int maxi = 0; 
    for(int x: A) maxi = max(maxi, x); 

    if(maxi <= 3) return subtask_4(A); 

    maxi = 0; 
    for(int x: A) c[x]++; 
    f(i,1,n+1) maxi = max(maxi, c[i]); 

    if(maxi <= 2) return subtask_5(A); 
    return subtask_3(A); 
}

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