제출 #766396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766396		KindaNameless	서열 (APIO23_sequence)	C++17	0 / 100	195 ms	166056 KiB

sequence

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

struct node{
    int val;
    node *L, *R;

    node(int _val){
        val = _val;
        L = R = nullptr;
    }

    node(node *_L, node *_R){
        L = _L; R = _R;
        val = 0;
        if(L)val += L->val;
        if(R)val += R->val;
    }
};

const int SZ = 100000;

node* build(int lx = 0, int rx = SZ - 1){
    if(lx == rx){
        return new node(0);
    }
    int m = (lx + rx) / 2;
    return new node(build(lx, m),
                    build(m + 1, rx));
}

node* upd(node *cur, int i, int lx = 0, int rx = SZ - 1){
    if(lx == rx){
        return new node(cur->val + 1);
    }
    int m = (lx + rx) / 2;
    if(i <= m){
        return new node(upd(cur->L, i, lx, m), cur->R);
    }
    return new node(cur->L, upd(cur->R, i, m + 1, rx));
}

int query(node *u, node *v, int k, int lx = 0, int rx = SZ - 1){
    if(lx == rx){
        return lx;
    }
    int m = (lx + rx) / 2, cnt = v->L->val - u->L->val;
    if(cnt >= k){
        return query(u->L, v->L, k, lx, m);
    }
    return query(u->R, v->R, k - cnt, m + 1, rx);
}

node* roots[SZ + 1];

inline bool can(int val, int l, int r){
    int len = r - l + 1;
    if(len & 1){
        return val == query(roots[l - 1], roots[r] , (len + 1) / 2);
    }
    else{
        return val == query(roots[l - 1], roots[r], len / 2) || val == query(roots[l - 1], roots[r], len / 2 + 1);
    }
}

int sequence(int N, vector<int> A){

    vector<vector<int>> pos(N + 1);

    roots[0] = build();

    int mx = 0;
    for(int i = 0; i < N; ++i){
        roots[i + 1] = upd(roots[i], A[i]);
        pos[A[i]].push_back(i + 1);
        mx = max(mx, A[i]);
    }

    int answer = 1;
    for(int i = 1; i <= N; ++i){
        int curmx = 1;
        for(int l = 0, r = 0; l < (int)pos[i].size(); ++l){
            while(r + 1 < (int)pos[i].size() && can(i, pos[i][l], pos[i][r+1])){
                r++;
            }
            curmx = max(curmx, r - l + 1);
        }
        answer = max(answer, curmx);
    }

    return answer;
}

//int main(){
//    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//    //cout << sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});
//    cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});
//
//    return 0;
//}

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