oj.uz

Submission #766396

# Submission time Handle Problem Language Result Execution time Memory
766396 2023-06-25T15:36:59 Z KindaNameless Sequence (APIO23_sequence) C++17
0 / 100
 195 ms 166056 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 6 ms 6484 KB Output is correct
4 Correct 5 ms 6520 KB Output is correct
5 Incorrect 8 ms 6612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 6 ms 6484 KB Output is correct
4 Correct 5 ms 6520 KB Output is correct
5 Incorrect 8 ms 6612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Runtime error 179 ms 161124 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Runtime error 162 ms 163804 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 ms 166056 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 6 ms 6484 KB Output is correct
4 Correct 5 ms 6520 KB Output is correct
5 Incorrect 8 ms 6612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 6 ms 6484 KB Output is correct
4 Correct 5 ms 6520 KB Output is correct
5 Incorrect 8 ms 6612 KB Output isn't correct
6 Halted 0 ms 0 KB -