oj.uz

Submission #72233

# Submission time Handle Problem Language Result Execution time Memory
72233 2018-08-26T06:13:24 Z cat > /dev/null(#2231, lobo_prix, jms100300, enochjung) Box Run (FXCUP3_box) C++17
17 / 100
 39 ms 3984 KB 
#include<iostream>
#include<algorithm>
#include<cstring>
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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 2 ms 1200 KB Output is correct
4 Correct 2 ms 1328 KB Output is correct
5 Correct 2 ms 1376 KB Output is correct
6 Correct 2 ms 1376 KB Output is correct
7 Correct 3 ms 1376 KB Output is correct
8 Correct 3 ms 1376 KB Output is correct
9 Correct 2 ms 1376 KB Output is correct
10 Correct 3 ms 1376 KB Output is correct
11 Correct 2 ms 1416 KB Output is correct

Subtask #2
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 2 ms 1200 KB Output is correct
4 Correct 2 ms 1328 KB Output is correct
5 Correct 2 ms 1376 KB Output is correct
6 Correct 2 ms 1376 KB Output is correct
7 Correct 3 ms 1376 KB Output is correct
8 Correct 3 ms 1376 KB Output is correct
9 Correct 2 ms 1376 KB Output is correct
10 Correct 3 ms 1376 KB Output is correct
11 Correct 2 ms 1416 KB Output is correct
12 Correct 3 ms 1416 KB Output is correct
13 Correct 4 ms 1416 KB Output is correct
14 Correct 19 ms 2112 KB Output is correct
15 Correct 29 ms 2556 KB Output is correct
16 Correct 39 ms 3092 KB Output is correct
17 Runtime error 19 ms 3984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -