oj.uz

답안 #756965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756965 2023-06-12T11:51:12 Z doowey 서열 (APIO23_sequence) C++17
28 / 100
 239 ms 4192 KB 
#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 2050;
int cnt[N];
int tree[N * 4 + 512];

void add(int node, int cl, int cr, int id){
    tree[node] ++ ;
    if(cl == cr){
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        add(node * 2, cl, mid, id);
    else
        add(node * 2 + 1, mid + 1, cr, id);
}

int find_idx(int node, int cl, int cr, int lim){
    if(cl == cr) {
        return tree[node];
    }
    int mid = (cl + cr) / 2;
    if(tree[node * 2] >= lim){
        return find_idx(node * 2, cl, mid, lim);
    }
    else{
        return find_idx(node * 2 + 1, mid + 1, cr, lim - tree[node * 2]);
    }
}

void init(int node, int cl, int cr){
    tree[node] = 0;
    if(cl == cr) return;
    int mid = (cl + cr) / 2;
    init(node * 2, cl, mid);
    init(node * 2 + 1, mid + 1, cr);
}

int sequence(int n, vector<int> a) {
    if(n > 2000){
        int las = -1;
        int cnt = 0;
        int res = 0;
        for(int i = 0 ; i < n; i ++ ){
            if(a[i] == las){
                cnt ++ ;
            }
            else{
                cnt = 1;
                las = a[i];
            }
            res = max(res, cnt);
        }
        return res;
    }
    int ans = 0;
    int sz;
    int me;
    for(int i = 0 ; i < n; i ++) {
        init(1, 1, n);
        for(int j = i ; j < n; j ++) {
            add(1, 1, n, a[j]);
            sz = j - i + 1;
            if(sz % 2 == 1){
                me = (sz + 1) / 2;
                ans = max(ans, find_idx(1, 1, n, me));
            }
            else{
                me = (sz + 1) / 2;
                ans = max(ans, find_idx(1, 1, n, me));
                ans = max(ans, find_idx(1, 1, n, me + 1));
            }
        }
    }
    return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 238 ms 316 KB Output is correct
14 Correct 223 ms 332 KB Output is correct
15 Correct 125 ms 320 KB Output is correct
16 Correct 130 ms 212 KB Output is correct
17 Correct 104 ms 312 KB Output is correct
18 Correct 239 ms 320 KB Output is correct
19 Correct 206 ms 316 KB Output is correct
20 Correct 175 ms 312 KB Output is correct
21 Correct 232 ms 312 KB Output is correct
22 Correct 234 ms 316 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 4172 KB Output is correct
3 Incorrect 41 ms 4192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 35 ms 4188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4172 KB Output is correct
2 Correct 42 ms 4188 KB Output is correct
3 Incorrect 48 ms 4172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 238 ms 316 KB Output is correct
14 Correct 223 ms 332 KB Output is correct
15 Correct 125 ms 320 KB Output is correct
16 Correct 130 ms 212 KB Output is correct
17 Correct 104 ms 312 KB Output is correct
18 Correct 239 ms 320 KB Output is correct
19 Correct 206 ms 316 KB Output is correct
20 Correct 175 ms 312 KB Output is correct
21 Correct 232 ms 312 KB Output is correct
22 Correct 234 ms 316 KB Output is correct
23 Incorrect 9 ms 880 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 238 ms 316 KB Output is correct
14 Correct 223 ms 332 KB Output is correct
15 Correct 125 ms 320 KB Output is correct
16 Correct 130 ms 212 KB Output is correct
17 Correct 104 ms 312 KB Output is correct
18 Correct 239 ms 320 KB Output is correct
19 Correct 206 ms 316 KB Output is correct
20 Correct 175 ms 312 KB Output is correct
21 Correct 232 ms 312 KB Output is correct
22 Correct 234 ms 316 KB Output is correct
23 Correct 49 ms 4172 KB Output is correct
24 Incorrect 41 ms 4192 KB Output isn't correct
25 Halted 0 ms 0 KB -