Submission #72212

#	Time	Username	Problem	Language	Result	Execution time	Memory
72212		cat > /dev/null (#118)	Box Run (FXCUP3_box)	C++17	17 / 100	61 ms	3852 KiB

box

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

const int MAX_N = 1e5;
pair<int, int> tmp[MAX_N];
int arr[MAX_N];
int res[MAX_N];

const int MAX_T = MAX_N+10;
int tree[MAX_T+1];

void update(int x, int val) {
    x = MAX_T - x - 1;
    tree[x] = val;

    for (int k = x; k <= MAX_T; k += (k & -k))
        tree[k] = max(tree[k], val);
}

int query(int x) {
    x = MAX_T - x - 1;
    int ret = -1;
    for (int k = x; k > 0; k -= (k & -k))
        ret = max(ret, tree[k]);
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    memset(tree, -1, sizeof tree);

    int N;  cin >> N;
    for (int i = 0; i < N; i ++) {
        cin >> arr[i];
        tmp[i].first = arr[i];
        tmp[i].second = i;
    }

    sort(tmp, tmp + N);
    int cur_idx = -1;
    int prv_val = -1;
    for (int i = 0; i < N; i ++) {
        if (prv_val != tmp[i].first) 
            cur_idx++;
        arr[tmp[i].second] = cur_idx;
        prv_val = tmp[i].first;
    }
    cur_idx ++;

    int last = 0;

    memset(res, -1, sizeof res);
    update(arr[0], 0);
    for (int i = 1; i < N; i ++) {
        if (arr[i] > arr[i-1]) { 
            int qidx = query(arr[i]);
            if (qidx != -1) {
                for (int k = qidx+1; k < i-last; k ++) 
                    res[i-k-1] = k+1;

                last = max(last, i-qidx-1);
            }
            else {
                for (; last < i; last ++)
                    res[last] = i-last;
            }
        }
        update(arr[i], i);
    }

    for (int i = 0; i < N; i ++)
        cout << res[i] << ' ';
    cout << endl;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 83