Submission #756947

#	Time	Username	Problem	Language	Result	Execution time	Memory
756947		doowey	Sequence (APIO23_sequence)	C++17	28 / 100	237 ms	8400 KiB

sequence

#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) {
    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 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18