oj.uz

Submission #1007372

# Submission time Handle Problem Language Result Execution time Memory
1007372 2024-06-24T17:29:08 Z c2zi6 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 12628 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "elephants.h"

int n;
int l;
int a[60000];
int b[60000];

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    rep(i, n) b[i] = a[i] = X[i];
    sort(b, b + n);
}

int m = 0;
int st[60000];
void replace(int x, int y) {
    while (b[n-1] > x) {
        st[m++] = b[--n];
    }
    --n;
    while (n && b[n-1] > y) {
        st[m++] = b[--n];
    }
    while (m && st[m-1] < y) {
        b[n++] = st[--m];
    }
    b[n++] = y;
    while (m) {
        b[n++] = st[--m];
    }
}

int update(int i, int y) {
    replace(a[i], y);
    a[i] = y;
    int R = -1e9;
    int ans = 0;
    for (int x : b) {
        if (x > R) ++ans, R = x+l;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 6 ms 8636 KB Output is correct
4 Correct 4 ms 8788 KB Output is correct
5 Correct 4 ms 8652 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 2320 ms 10588 KB Output is correct
8 Correct 3159 ms 10740 KB Output is correct
9 Correct 2765 ms 10832 KB Output is correct
10 Correct 4482 ms 10844 KB Output is correct
11 Correct 4780 ms 12124 KB Output is correct
12 Correct 5828 ms 12124 KB Output is correct
13 Correct 5007 ms 11984 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 6 ms 8636 KB Output is correct
4 Correct 4 ms 8788 KB Output is correct
5 Correct 4 ms 8652 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 2320 ms 10588 KB Output is correct
8 Correct 3159 ms 10740 KB Output is correct
9 Correct 2765 ms 10832 KB Output is correct
10 Correct 4482 ms 10844 KB Output is correct
11 Correct 4780 ms 12124 KB Output is correct
12 Correct 5828 ms 12124 KB Output is correct
13 Correct 5007 ms 11984 KB Output is correct
14 Correct 3239 ms 12248 KB Output is correct
15 Correct 5536 ms 12124 KB Output is correct
16 Execution timed out 9061 ms 12628 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 6 ms 8636 KB Output is correct
4 Correct 4 ms 8788 KB Output is correct
5 Correct 4 ms 8652 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 2320 ms 10588 KB Output is correct
8 Correct 3159 ms 10740 KB Output is correct
9 Correct 2765 ms 10832 KB Output is correct
10 Correct 4482 ms 10844 KB Output is correct
11 Correct 4780 ms 12124 KB Output is correct
12 Correct 5828 ms 12124 KB Output is correct
13 Correct 5007 ms 11984 KB Output is correct
14 Correct 3239 ms 12248 KB Output is correct
15 Correct 5536 ms 12124 KB Output is correct
16 Execution timed out 9061 ms 12628 KB Time limit exceeded
17 Halted 0 ms 0 KB -