Submission #1130882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130882		79brue	Sequence (APIO23_sequence)	C++20	12 / 100	809 ms	58360 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Node{
    int sum, prf, suf;
    Node(){}
    Node(int sum, int prf, int suf): sum(sum), prf(prf), suf(suf){}
    Node(int x){
        sum = x;
        prf = suf = max(x, 0);
    }

    Node operator+(const Node &r)const{
        return Node(sum + r.sum, max(prf, sum + r.prf), max(suf + r.sum, r.suf));
    }
};

struct segTree{
    Node tree[1<<20];

    void init(int i, int l, int r, int v){
        if(l==r){
            tree[i] = Node(v);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, v);
        init(i*2+1, m+1, r, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i] = Node(v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    Node query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return Node(0, 0, 0);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }
} treeMax, treeMin; /// +0-, -0+

int n;

void update_zero(int x){
    treeMax.update(1, 1, n, x, 0);
    treeMin.update(1, 1, n, x, 0);
}

void update_one(int x){
    treeMax.update(1, 1, n, x, -1);
    treeMin.update(1, 1, n, x, 1);
}

int arr[500002];
vector<int> occ[500002];

int loc[500002];
int prf1[500002], suf1[500002], btw1[500002];
int prf2[500002], suf2[500002], btw2[500002];

bool able(int L, int k){
    int sum1 = 0, sum2 = 0;
    for(int i=1; i<=L-2; i++) sum1 += btw1[i], sum2 += btw2[i];

    for(int s=1; s+L-1 <= k; s++){
        int e = s+L-1;
        sum1 += btw1[e-1] - btw1[s-1], sum2 += btw2[e-1] - btw2[s-1];
        int v1 = sum1 + prf1[s] + suf1[e], v2 = sum2 + prf2[s] + suf2[e];
        if(v1 >= -L && v2 >= -L) return true;
    }
    return false;
}

int sequence(int _N, vector<int> A){
    n = _N;
    for(int i=1; i<=n; i++){
        arr[i] = A[i-1];
        occ[arr[i]].push_back(i);
    }
    treeMax.init(1, 1, n, 1), treeMin.init(1, 1, n, -1);

    int ans = 1;

    for(int v=1; v<=n; v++){
        if(occ[v].empty()) continue;

        int k = (int)occ[v].size();
        for(int i=1; i<=k; i++) loc[i] = occ[v][i-1];
        loc[0] = 0, loc[k+1] = n+1;

        for(int i=1; i<=k; i++) update_zero(loc[i]);

        for(int i=0; i<=k; i++){
            int s = loc[i]+1, e = loc[i+1]-1;
            Node p1 = treeMax.query(1, 1, n, s, e), p2 = treeMin.query(1, 1, n, s, e);
            if(i) prf1[i] = p1.prf, prf2[i] = p2.prf;
            if(i<k) suf1[i+1] = p1.suf, suf2[i+1] = p2.suf;
            if(i && i<k) btw1[i] = p1.sum, btw2[i] = p2.sum;
        }

        int MIN = ans + 1, MAX = k, ANS = 1;
        while(MIN <= MAX){
            int MID = (MIN + MAX) / 2;
            if(able(MID, k)) ANS = MID, MIN = MID + 1;
            else MAX = MID - 1;
        }

        ans = max(ans, ANS);

        for(int i=1; i<=k; i++) update_one(loc[i]);
    }

    return ans;
}

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