oj.uz

Submission #101837

# Submission time Handle Problem Language Result Execution time Memory
101837 2019-03-20T12:45:39 Z alexpetrescu Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 7204 KB 
#include "elephants.h"
#include <vector>
#include <algorithm>
 
#define MAXN 150000
#define MAXR 110
#define LOGR 6
#define MAXK 1400
#define LOGK 11
 
bool seen;
int n, l, k, r, mareleCnt;
std::vector < int > v[MAXR];
int u[MAXN], p[MAXN], poz[MAXN];
struct myc {
    int x, y;
} dp[MAXN];
 
inline void calc(std::vector < int > &t) {
    int j = t.size() - 1;
    for (int i = t.size() - 1; i >= 0; i--) {
        if (u[t[i]] + l >= u[t.back()]) dp[t[i]] = {1, u[t[i]] + l};
        else {
            while (j - 1 > i && u[t[j - 1]] > u[t[i]] + l)
                j--;
            dp[t[i]] = {1 + dp[t[j]].x, dp[t[j]].y};
        }
    }
}
 
void init(int N, int L, int X[]) {
    if (seen == 0) {
        n = N;
        l = L;
        k = MAXK;
        seen = 1;
        for (int i = 0; i < n; i++)
            p[i] = i;
        for (int i = 0; i < n; i++)
            u[i] = X[i];
    }
    r = 1 + (n - 1) / k;
    for (int i = 0; i < r; i++) {
        v[i].resize(std::min(n, (i + 1) * k) - i * k);
        for (int j = i * k; j < n && j < (i + 1) * k; j++)
            v[i][j - i * k] = p[j], poz[p[j]] = i;
    }
    for (int i = r - 1; i >= 0; i--)
        calc(v[i]);
}
 
inline void myInit() {
    int aici[1] = {0};
    int j = 0;
    for (int i = 0; i < r; i++)
        for (auto &x : v[i])
            p[j++] = x;
    init(0, 0, aici);
}
 
inline void scoate(int p) {
    int i = 0;
    while (v[poz[p]][i] != p)
        i++;
    while (i + 1 < (int)v[poz[p]].size()) {
        v[poz[p]][i] = v[poz[p]][i + 1];
        i++;
    }
    v[poz[p]].pop_back();
}
 
inline void baga(int p) {
    int i = 0;
    while (i < (int)v[poz[p]].size() && u[v[poz[p]][i]] < u[p])
        i++;
    v[poz[p]].push_back(0);
    for (int j = v[poz[p]].size() - 1; j > i; j--)
        v[poz[p]][j] = v[poz[p]][j - 1];
    v[poz[p]][i] = p;
}
 
int update(int i, int y) {
    int e = 0, f = poz[i];
    for (int pas = 1 << LOGR; pas; pas >>= 1)
        if (e + pas < r && u[v[e + pas][0]] <= y)
            e += pas;
 
    scoate(i);
    poz[i] = e;
    u[i] = y;
    baga(i);
 
    mareleCnt++;
    if (mareleCnt % k == 0)
        myInit();
    else if (f == e)
        calc(v[e]);
    else if (((int)v[f].size() == 0 && f != r - 1) || (int)v[e].size() == 2 * r)
        myInit();
    else if (e < f) {
        if ((int)v[f].size() == 0)
            r--;
        else
            calc(v[f]);
        calc(v[e]);
    } else {
        calc(v[e]);
        calc(v[f]);
    }
 
    int val = -1, ans = 0;
    for (int i = 0; i < r; i++) {
        if (val < u[v[i].back()]) {
            int rez = -1;
            for (int pas = 1 << LOGK; pas; pas >>= 1)
                if (rez + pas < (int)v[i].size() && u[v[i][rez + pas]] <= val)
                    rez += pas;
            rez++;
            ans += dp[v[i][rez]].x;
            val = dp[v[i][rez]].y;
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 653 ms 1784 KB Output is correct
8 Correct 638 ms 1912 KB Output is correct
9 Correct 692 ms 2836 KB Output is correct
10 Correct 730 ms 2680 KB Output is correct
11 Correct 817 ms 2680 KB Output is correct
12 Correct 1884 ms 2904 KB Output is correct
13 Correct 850 ms 2728 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 653 ms 1784 KB Output is correct
8 Correct 638 ms 1912 KB Output is correct
9 Correct 692 ms 2836 KB Output is correct
10 Correct 730 ms 2680 KB Output is correct
11 Correct 817 ms 2680 KB Output is correct
12 Correct 1884 ms 2904 KB Output is correct
13 Correct 850 ms 2728 KB Output is correct
14 Correct 884 ms 2168 KB Output is correct
15 Correct 927 ms 2228 KB Output is correct
16 Correct 3604 ms 3232 KB Output is correct
17 Correct 3512 ms 3832 KB Output is correct
18 Correct 3873 ms 3832 KB Output is correct
19 Correct 1566 ms 3704 KB Output is correct
20 Correct 3297 ms 3796 KB Output is correct
21 Correct 3330 ms 3832 KB Output is correct
22 Correct 1591 ms 3320 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 653 ms 1784 KB Output is correct
8 Correct 638 ms 1912 KB Output is correct
9 Correct 692 ms 2836 KB Output is correct
10 Correct 730 ms 2680 KB Output is correct
11 Correct 817 ms 2680 KB Output is correct
12 Correct 1884 ms 2904 KB Output is correct
13 Correct 850 ms 2728 KB Output is correct
14 Correct 884 ms 2168 KB Output is correct
15 Correct 927 ms 2228 KB Output is correct
16 Correct 3604 ms 3232 KB Output is correct
17 Correct 3512 ms 3832 KB Output is correct
18 Correct 3873 ms 3832 KB Output is correct
19 Correct 1566 ms 3704 KB Output is correct
20 Correct 3297 ms 3796 KB Output is correct
21 Correct 3330 ms 3832 KB Output is correct
22 Correct 1591 ms 3320 KB Output is correct
23 Correct 4964 ms 7104 KB Output is correct
24 Correct 5231 ms 7084 KB Output is correct
25 Correct 4122 ms 7204 KB Output is correct
26 Execution timed out 9065 ms 6720 KB Time limit exceeded
27 Halted 0 ms 0 KB -