oj.uz

Submission #413026

# Submission time Handle Problem Language Result Execution time Memory
413026 2021-05-28T05:14:14 Z ja_kingy Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8776 ms 11872 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int SQRT = 500, mxN = 150000;
int n, x[mxN+1], l, req[mxN], nx[mxN], blk[mxN], ucnt;
vector<int> blocks[SQRT];

void build_block(int b) {
    int ne = blocks[b].size();
    for (int i = blocks[b].size(); i--;) {
        while (x[blocks[b][ne-1]] > x[blocks[b][i]] + l) ne--;
        req[blocks[b][i]] = ne == blocks[b].size() ? 1 : req[blocks[b][ne]] + 1;
        nx[blocks[b][i]] = ne == blocks[b].size() ? x[blocks[b][i]] + l + 1 : nx[blocks[b][ne]];
    }
}

void rebuild() {
    for (int i = 0; i < (n+SQRT-1)/SQRT; ++i) {
        blocks[i].clear();
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){return x[a] < x[b];});
    int b = 0;
    for (int i = 0; i < n; ++i) {
        blocks[b].push_back(order[i]);
        blk[order[i]] = b;
        if (blocks[b].size() == SQRT || i == n-1) {
            build_block(b);
            b++;
        }
    }
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    copy(X, X+n, x);
    rebuild();
}

int update(int i, int y) {
    ucnt++;
    if (ucnt == SQRT) {
        ucnt = 0;
        rebuild();
    }
    blocks[blk[i]].erase(find(blocks[blk[i]].begin(), blocks[blk[i]].end(), i));
    build_block(blk[i]);
    x[i] = y;
    for (int b = 0; b < (n+SQRT-1)/SQRT; ++b) {
        if (b == (n+SQRT-1)/SQRT-1 || blocks[b].size() && x[blocks[b].back()] >= y) {
            blk[i] = b;
            blocks[b].insert(lower_bound(blocks[b].begin(), blocks[b].end(), i, [&](int a, int b){return x[a] < x[b];}), i);
            build_block(b);
            break;                        
        }
    }
    int ans = 0;
    x[n] = 0;
    for (int b = 0; b < (n+SQRT-1)/SQRT; ++b) {
        auto it = lower_bound(blocks[b].begin(), blocks[b].end(), n, [&](int a, int b){return x[a] < x[b];});
        if (it != blocks[b].end()) {
            ans += req[*it];
            x[n] = nx[*it];
        }
    }
    return ans;
}

Compilation message

elephants.cpp: In function 'void build_block(int)':
elephants.cpp:13:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         req[blocks[b][i]] = ne == blocks[b].size() ? 1 : req[blocks[b][ne]] + 1;
      |                             ~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:14:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         nx[blocks[b][i]] = ne == blocks[b].size() ? x[blocks[b][i]] + l + 1 : nx[blocks[b][ne]];
      |                            ~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:53:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   53 |         if (b == (n+SQRT-1)/SQRT-1 || blocks[b].size() && x[blocks[b].back()] >= y) {
      |                                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 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 1 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 1 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 1 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 1 ms 332 KB Output is correct
7 Correct 486 ms 1328 KB Output is correct
8 Correct 525 ms 1488 KB Output is correct
9 Correct 674 ms 2420 KB Output is correct
10 Correct 843 ms 2360 KB Output is correct
11 Correct 852 ms 2312 KB Output is correct
12 Correct 1260 ms 2420 KB Output is correct
13 Correct 856 ms 2312 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 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 1 ms 332 KB Output is correct
7 Correct 486 ms 1328 KB Output is correct
8 Correct 525 ms 1488 KB Output is correct
9 Correct 674 ms 2420 KB Output is correct
10 Correct 843 ms 2360 KB Output is correct
11 Correct 852 ms 2312 KB Output is correct
12 Correct 1260 ms 2420 KB Output is correct
13 Correct 856 ms 2312 KB Output is correct
14 Correct 753 ms 1736 KB Output is correct
15 Correct 788 ms 2112 KB Output is correct
16 Correct 2007 ms 2656 KB Output is correct
17 Correct 2250 ms 3376 KB Output is correct
18 Correct 2407 ms 3252 KB Output is correct
19 Correct 1474 ms 3092 KB Output is correct
20 Correct 2250 ms 3264 KB Output is correct
21 Correct 2204 ms 3260 KB Output is correct
22 Correct 1490 ms 3168 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 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 1 ms 332 KB Output is correct
7 Correct 486 ms 1328 KB Output is correct
8 Correct 525 ms 1488 KB Output is correct
9 Correct 674 ms 2420 KB Output is correct
10 Correct 843 ms 2360 KB Output is correct
11 Correct 852 ms 2312 KB Output is correct
12 Correct 1260 ms 2420 KB Output is correct
13 Correct 856 ms 2312 KB Output is correct
14 Correct 753 ms 1736 KB Output is correct
15 Correct 788 ms 2112 KB Output is correct
16 Correct 2007 ms 2656 KB Output is correct
17 Correct 2250 ms 3376 KB Output is correct
18 Correct 2407 ms 3252 KB Output is correct
19 Correct 1474 ms 3092 KB Output is correct
20 Correct 2250 ms 3264 KB Output is correct
21 Correct 2204 ms 3260 KB Output is correct
22 Correct 1490 ms 3168 KB Output is correct
23 Correct 4712 ms 6208 KB Output is correct
24 Correct 5097 ms 11244 KB Output is correct
25 Correct 4165 ms 11256 KB Output is correct
26 Correct 5926 ms 11260 KB Output is correct
27 Correct 6475 ms 11108 KB Output is correct
28 Correct 2059 ms 5312 KB Output is correct
29 Correct 2012 ms 5192 KB Output is correct
30 Correct 2061 ms 5256 KB Output is correct
31 Correct 2008 ms 5228 KB Output is correct
32 Correct 6030 ms 10692 KB Output is correct
33 Correct 6336 ms 9976 KB Output is correct
34 Correct 5997 ms 10888 KB Output is correct
35 Correct 5272 ms 11872 KB Output is correct
36 Correct 4247 ms 10660 KB Output is correct
37 Correct 8082 ms 11656 KB Output is correct
38 Correct 5970 ms 9892 KB Output is correct
39 Correct 5924 ms 10928 KB Output is correct
40 Correct 6077 ms 9924 KB Output is correct
41 Correct 8755 ms 10728 KB Output is correct
42 Correct 8776 ms 10904 KB Output is correct