oj.uz

Submission #1118493

# Submission time Handle Problem Language Result Execution time Memory
1118493 2024-11-25T14:56:12 Z _callmelucian Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 18556 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 = 50, resetCycle = 20;
const int blockSize = 500, resetCycle = 200, 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();
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8548 KB Output is correct
3 Correct 2 ms 8544 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8548 KB Output is correct
3 Correct 2 ms 8544 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 6290 ms 2476 KB Output is correct
8 Correct 7985 ms 10348 KB Output is correct
9 Correct 257 ms 3700 KB Output is correct
10 Correct 3552 ms 4196 KB Output is correct
11 Correct 3382 ms 4220 KB Output is correct
12 Correct 3615 ms 13348 KB Output is correct
13 Correct 3556 ms 5792 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8548 KB Output is correct
3 Correct 2 ms 8544 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 6290 ms 2476 KB Output is correct
8 Correct 7985 ms 10348 KB Output is correct
9 Correct 257 ms 3700 KB Output is correct
10 Correct 3552 ms 4196 KB Output is correct
11 Correct 3382 ms 4220 KB Output is correct
12 Correct 3615 ms 13348 KB Output is correct
13 Correct 3556 ms 5792 KB Output is correct
14 Correct 4548 ms 10948 KB Output is correct
15 Correct 265 ms 6996 KB Output is correct
16 Correct 657 ms 4712 KB Output is correct
17 Correct 1753 ms 5828 KB Output is correct
18 Correct 3406 ms 5080 KB Output is correct
19 Correct 7190 ms 15276 KB Output is correct
20 Correct 1705 ms 14796 KB Output is correct
21 Correct 6469 ms 14464 KB Output is correct
22 Correct 7195 ms 14564 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8548 KB Output is correct
3 Correct 2 ms 8544 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 6290 ms 2476 KB Output is correct
8 Correct 7985 ms 10348 KB Output is correct
9 Correct 257 ms 3700 KB Output is correct
10 Correct 3552 ms 4196 KB Output is correct
11 Correct 3382 ms 4220 KB Output is correct
12 Correct 3615 ms 13348 KB Output is correct
13 Correct 3556 ms 5792 KB Output is correct
14 Correct 4548 ms 10948 KB Output is correct
15 Correct 265 ms 6996 KB Output is correct
16 Correct 657 ms 4712 KB Output is correct
17 Correct 1753 ms 5828 KB Output is correct
18 Correct 3406 ms 5080 KB Output is correct
19 Correct 7190 ms 15276 KB Output is correct
20 Correct 1705 ms 14796 KB Output is correct
21 Correct 6469 ms 14464 KB Output is correct
22 Correct 7195 ms 14564 KB Output is correct
23 Correct 1505 ms 18540 KB Output is correct
24 Correct 1429 ms 11348 KB Output is correct
25 Correct 1039 ms 10892 KB Output is correct
26 Execution timed out 9038 ms 18556 KB Time limit exceeded
27 Halted 0 ms 0 KB -