oj.uz

Submission #1118499

# Submission time Handle Problem Language Result Execution time Memory
1118499 2024-11-25T15:04:39 Z _callmelucian Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 20236 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int blockSize = 400, resetCycle = 400, mn = 150'005;
int n, L, queryCount, save[mn];

struct block {
    vector<int> x, jumpTo, step;

    void refine() {
        int iter = x.size();
        for (int i = (int)x.size() - 1; i >= 0; i--) {
            while (iter - 1 >= 0 && x[iter - 1] - x[i] > L) iter--;
            if (iter == x.size()) jumpTo[i] = x[i] + L, step[i] = 1;
            else jumpTo[i] = jumpTo[iter], step[i] = step[iter] + 1;
        }
    }

    block (vector<int> x) : x(x), jumpTo(x.size()), step(x.size()) { refine(); }

    void insert (int xP) {
        x.insert(upper_bound(all(x), xP), xP);
        jumpTo.push_back(0), step.push_back(0);
        refine();
    }

    void remove (int xP) {
        x.erase(lower_bound(all(x), xP));
        jumpTo.pop_back(), step.pop_back();
        refine();
    }

    pii batchJump (int start) {
        int pos = upper_bound(all(x), start) - x.begin();
        if (pos == x.size()) return {start, 0};
        return {jumpTo[pos], step[pos]};
    }

    int last() { return x.back(); }
};

vector<block> blocks;

void build (const vector<int> &x) {
    for (int i = 0; i < x.size(); i += blockSize) {
        vector<int> cur(x.begin() + i, x.begin() + min((int)x.size(), i + blockSize));
        blocks.emplace_back(cur);
    }
}

void reBuild() {
    vector<int> x;
    for (block &cur : blocks)
        for (int u : cur.x) x.push_back(u);
    blocks.clear(), build(x);
}

void insert (int xP) {
    for (block &cur : blocks)
        if (cur.last() >= xP) return cur.insert(xP), void();
    blocks[(int)blocks.size() - 1].insert(xP);
}

void remove (int xP) {
    for (block &cur : blocks)
        if (cur.last() >= xP) return cur.remove(xP), void();
}

int query() {
    int curPos = -1, ans = 0;
    for (block &cur : blocks) {
        int newPos, step; tie(newPos, step) = cur.batchJump(curPos);
        curPos = newPos, ans += step;
    }
    return ans;
}

void init (int _n, int _L, int X[]) {
    n = _n, L = _L;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) vec[i] = save[i] = X[i];
    build(vec);
}

int update (int i, int y) {
    if (queryCount && (queryCount++) % resetCycle == 0) reBuild();
    remove(save[i]), insert(y), save[i] = y;
    return query();
}

#ifdef LOCAL
int main()
{
    freopen("ELEPHANTS.inp", "r", stdin);
    freopen("ELEPHANTS.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    int q; cin >> n >> L >> q;
    vector<int> x(n);

    for (int i = 0; i < n; i++) cin >> x[i];
    build(x);

    for (int i = 0; i < q; i++) {
        if (i && i % resetCycle == 0) reBuild();
        int pos, y; cin >> pos >> y;
        remove(x[pos]), insert(y);
        x[pos] = y;
        cout << query() << "\n";
    }

    return 0;
}
#endif // LOCAL

Compilation message

elephants.cpp: In member function 'void block::refine()':
elephants.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             if (iter == x.size()) jumpTo[i] = x[i] + L, step[i] = 1;
      |                 ~~~~~^~~~~~~~~~~
elephants.cpp: In member function 'pii block::batchJump(int)':
elephants.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (pos == x.size()) return {start, 0};
      |             ~~~~^~~~~~~~~~~
elephants.cpp: In function 'void build(const std::vector<int>&)':
elephants.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < x.size(); i += blockSize) {
      |                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5887 ms 2480 KB Output is correct
8 Correct 8164 ms 10272 KB Output is correct
9 Correct 271 ms 3704 KB Output is correct
10 Correct 3582 ms 13500 KB Output is correct
11 Correct 3510 ms 4156 KB Output is correct
12 Correct 3652 ms 13312 KB Output is correct
13 Correct 3489 ms 3788 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5887 ms 2480 KB Output is correct
8 Correct 8164 ms 10272 KB Output is correct
9 Correct 271 ms 3704 KB Output is correct
10 Correct 3582 ms 13500 KB Output is correct
11 Correct 3510 ms 4156 KB Output is correct
12 Correct 3652 ms 13312 KB Output is correct
13 Correct 3489 ms 3788 KB Output is correct
14 Correct 4954 ms 11060 KB Output is correct
15 Correct 280 ms 3428 KB Output is correct
16 Correct 553 ms 4624 KB Output is correct
17 Correct 1826 ms 5828 KB Output is correct
18 Correct 3419 ms 4968 KB Output is correct
19 Correct 7292 ms 15232 KB Output is correct
20 Correct 1814 ms 5684 KB Output is correct
21 Correct 6418 ms 14376 KB Output is correct
22 Correct 7135 ms 14472 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5887 ms 2480 KB Output is correct
8 Correct 8164 ms 10272 KB Output is correct
9 Correct 271 ms 3704 KB Output is correct
10 Correct 3582 ms 13500 KB Output is correct
11 Correct 3510 ms 4156 KB Output is correct
12 Correct 3652 ms 13312 KB Output is correct
13 Correct 3489 ms 3788 KB Output is correct
14 Correct 4954 ms 11060 KB Output is correct
15 Correct 280 ms 3428 KB Output is correct
16 Correct 553 ms 4624 KB Output is correct
17 Correct 1826 ms 5828 KB Output is correct
18 Correct 3419 ms 4968 KB Output is correct
19 Correct 7292 ms 15232 KB Output is correct
20 Correct 1814 ms 5684 KB Output is correct
21 Correct 6418 ms 14376 KB Output is correct
22 Correct 7135 ms 14472 KB Output is correct
23 Correct 1466 ms 18696 KB Output is correct
24 Correct 1633 ms 13028 KB Output is correct
25 Correct 1147 ms 10772 KB Output is correct
26 Execution timed out 9043 ms 20236 KB Time limit exceeded
27 Halted 0 ms 0 KB -