oj.uz

Submission #833726

# Submission time Handle Problem Language Result Execution time Memory
833726 2023-08-22T08:16:55 Z kevinsogo Dancing Elephants (IOI11_elephants) C++17
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;
#include "elephants.h"
using ll = long long;

#ifdef LOCAL
bool debug = true;
#else
bool debug = false;
#endif

int n, L;
vector<int> x, best;

void init(int N, int L, int X[]) {
    n = N;
    ::L = L;
    x.resize(n);
    best.resize(n + 1);
    for (int i = 0; i < n; i++) {
        x[i] = X[i];
    }
}

int update(int i, int y) {
    if (debug) { cerr << "DOING UPDATE " << i << " " << y << endl; }
    if (debug) { cerr << "INITIALLY:    "; }
    if (debug) { for (int t = 0; t < n; t++) cerr << x[t] << " "; cerr << endl; }
    x[i] = y;
    while (i + 1 < n and x[i] > x[i + 1]) {
        swap(x[i], x[i + 1]);
        i++;
    }
    while (i - 1 >= 0 and x[i - 1] > x[i]) {
        swap(x[i - 1], x[i]);
        i--;
    }
    if (debug) { cerr << "AFTER UPDATE: "; }
    if (debug) { for (int t = 0; t < n; t++) cerr << x[t] << " "; cerr << endl; }

    int prev = -1;

    for (int i = 0; i < n; i++) {
        while (prev + 1 < i and x[prev + 1] <= x[i] - L - 1) {
            prev++;
        }
        best[i + 1] = best[prev + 1] + 1;
    }
    return best[n];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -