Submission #1130898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130898		79brue	Sequence (APIO23_sequence)	C++20	100 / 100	1086 ms	93876 KiB

sequence

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

using namespace std;

typedef long long ll;
const int INF = 1e9;

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+

struct minTree{
    int tree[1<<21];

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

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i] = min(tree[i], 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] = min(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return INF;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

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];
int S1[500002], T1[500002];
int S2[500002], T2[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 + suf1[s] + prf1[e], v2 = sum2 + suf2[s] + prf2[e];
        if(v1 >= -L && v2 >= -L) return true;
    }
    return false;
}

struct Query{
    int x, y, idx, type;
    Query(){}
    Query(int x, int y, int idx, int type): x(x), y(y), idx(idx), type(type){}

    bool operator<(const Query &r)const{
        if(y!=r.y) return y<r.y;
        if(type!=r.type) return type<r.type;
        return x<r.x;
    }
};

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+1] = btw1[i] + p1.sum + 1, btw2[i+1] = btw2[i] + p2.sum + 1;
        }

        for(int i=1; i<=k; i++){
            S1[i] = btw1[i] - suf1[i], S2[i] = btw2[i] - suf2[i];
            T1[i] = btw1[i] + prf1[i] + 1, T2[i] = btw2[i] + prf2[i] + 1;
        }

        /// (S1, S2) <= (T1, T2)인 점 찾기
        vector<int> xVal, yVal;
        for(int i=1; i<=k; i++){
            xVal.push_back(S1[i]), xVal.push_back(T1[i]);
            yVal.push_back(S2[i]), yVal.push_back(T2[i]);
        }
        sort(xVal.begin(), xVal.end());
        sort(yVal.begin(), yVal.end());
        xVal.erase(unique(xVal.begin(), xVal.end()), xVal.end());
        yVal.erase(unique(yVal.begin(), yVal.end()), yVal.end());

        int X = (int)xVal.size();
        for(int i=1; i<=k; i++){
            S1[i] = lower_bound(xVal.begin(), xVal.end(), S1[i]) - xVal.begin() + 1;
            T1[i] = lower_bound(xVal.begin(), xVal.end(), T1[i]) - xVal.begin() + 1;
            S2[i] = lower_bound(yVal.begin(), yVal.end(), S2[i]) - yVal.begin() + 1;
            T2[i] = lower_bound(yVal.begin(), yVal.end(), T2[i]) - yVal.begin() + 1;
        }

        vector<Query> vec;
        for(int i=1; i<=k; i++){
            vec.push_back(Query(S1[i], S2[i], i, 0));
            vec.push_back(Query(T1[i], T2[i], i, 1));
        }
        sort(vec.begin(), vec.end());

        tree.init(1, 1, X);
        for(Query &p: vec){
            if(p.type == 0) tree.update(1, 1, X, p.x, p.idx);
            else ans = max(ans, p.idx - tree.query(1, 1, X, 1, p.x) + 1);
        }

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

    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