oj.uz

Submission #941616

# Submission time Handle Problem Language Result Execution time Memory
941616 2024-03-09T07:59:08 Z wii Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 9824 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
#define lx (id << 1)
#define rx (lx | 1)
#define gcd __gcd
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }
 
const ll Linf = 0x3f3f3f3f3f3f3f3f;
const int Inf = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const ll Mod2 = ll(1e9) + 9;
const int Lim = 1e6 + 5;
const int inv6 = 166666668;
 
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
 
const int base = 3;
const int MaxN = 2e5 + 5;
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};
const int block_size = sqrt(2e9) + 2;
 
int n, len;
int val[MaxN];
int order[MaxN];
 
void init(int N, int L, int *x);
int update(int i, int y);
 
void init(int N, int L, int *x) {
    n = N;
    len = L;
 
    for (int i = 0; i < N; ++i)
        val[i] = x[i];
 
    for (int i = 0; i < N; ++i)
        order[i] = val[i];
 
    sort(order, order + N);
}
 
int update(int i, int y) {
    int t = val[i];
    for (int i = 0; i < n; ++i) if (order[i] == t) {
        for (int j = i; j < n; ++j)
            order[j] = order[j + 1];
    }
 
    order[n - 1] = y;
    for (int i = n - 1; i > 0; --i)
        if (order[i] < order[i - 1])
            swap(order[i], order[i - 1]);
 
    int res = 0, lf = -Inf;
    for (int i = 0; i < n; ++i) {
        if (lf + len < order[i])
            ++res, lf = order[i];
    }
 
    val[i] = y;
    return res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8644 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2497 ms 9328 KB Output is correct
8 Correct 3936 ms 9444 KB Output is correct
9 Correct 7462 ms 9824 KB Output is correct
10 Correct 5498 ms 9820 KB Output is correct
11 Correct 5613 ms 9564 KB Output is correct
12 Execution timed out 9097 ms 9808 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8644 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2497 ms 9328 KB Output is correct
8 Correct 3936 ms 9444 KB Output is correct
9 Correct 7462 ms 9824 KB Output is correct
10 Correct 5498 ms 9820 KB Output is correct
11 Correct 5613 ms 9564 KB Output is correct
12 Execution timed out 9097 ms 9808 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8644 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2497 ms 9328 KB Output is correct
8 Correct 3936 ms 9444 KB Output is correct
9 Correct 7462 ms 9824 KB Output is correct
10 Correct 5498 ms 9820 KB Output is correct
11 Correct 5613 ms 9564 KB Output is correct
12 Execution timed out 9097 ms 9808 KB Time limit exceeded
13 Halted 0 ms 0 KB -