oj.uz

Submission #448605

# Submission time Handle Problem Language Result Execution time Memory
448605 2021-07-31T05:57:52 Z dxz05 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 2640 KB 
#pragma GCC optimize("Ofast,unroll-loops,O2")
#pragma GCC target("avx,avx2")

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 3e2;

int N, L;
int X[MAXN], A[MAXN];
void init(int _N, int _L, int _X[]){
    N = _N;
    L = _L;
    for (int i = 0; i < N; i++) X[i] = _X[i];

    for (int i = 0; i < N; i++) A[i] = X[i];

    sort(A, A + N);

}

int lastans = -1;

int update(int pos, int val){
    if (X[pos] == val && lastans != -1) return lastans;

    int ind = find(A, A + N, X[pos]) - A;
    A[ind] = val;

    if (X[pos] < val) {
        while (ind < N - 1 && A[ind] > A[ind + 1]) {
            swap(A[ind], A[ind + 1]);
            ind++;
        }
    } else {
        while (ind > 0 && A[ind] < A[ind - 1]) {
            swap(A[ind], A[ind - 1]);
            ind--;
        }
    }

    X[pos] = val;

    //for (int i = 0; i < N; i++) cerr << X[i] << ' '; cerr << endl;
    //for (int i = 0; i < N; i++) cerr << A[i] << ' '; cerr << endl << endl;

    int ans = 1, last = A[0];
    int i = 0;

    while (i < N){
        if (A[i] - last > L){
            last = A[i];
            ans++;
        }
        i++;
    }

    lastans = ans;
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 877 ms 1044 KB Output is correct
8 Correct 1422 ms 1104 KB Output is correct
9 Correct 1648 ms 1484 KB Output is correct
10 Correct 4216 ms 1488 KB Output is correct
11 Correct 4073 ms 2632 KB Output is correct
12 Correct 7622 ms 2640 KB Output is correct
13 Correct 4692 ms 2596 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 877 ms 1044 KB Output is correct
8 Correct 1422 ms 1104 KB Output is correct
9 Correct 1648 ms 1484 KB Output is correct
10 Correct 4216 ms 1488 KB Output is correct
11 Correct 4073 ms 2632 KB Output is correct
12 Correct 7622 ms 2640 KB Output is correct
13 Correct 4692 ms 2596 KB Output is correct
14 Correct 1608 ms 2492 KB Output is correct
15 Correct 3111 ms 2420 KB Output is correct
16 Execution timed out 9022 ms 2628 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 877 ms 1044 KB Output is correct
8 Correct 1422 ms 1104 KB Output is correct
9 Correct 1648 ms 1484 KB Output is correct
10 Correct 4216 ms 1488 KB Output is correct
11 Correct 4073 ms 2632 KB Output is correct
12 Correct 7622 ms 2640 KB Output is correct
13 Correct 4692 ms 2596 KB Output is correct
14 Correct 1608 ms 2492 KB Output is correct
15 Correct 3111 ms 2420 KB Output is correct
16 Execution timed out 9022 ms 2628 KB Time limit exceeded
17 Halted 0 ms 0 KB -