oj.uz

Submission #1118514

# Submission time Handle Problem Language Result Execution time Memory
1118514 2024-11-25T15:30:33 Z _callmelucian Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16544 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 = 800, resetCycle = 200, mn = 150'005;
int n, L, queryCount, save[mn];

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

    void refine (int pos) {
        int iter = upper_bound(all(x), x[pos] + L) - x.begin();
        for (int i = pos; 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((int)x.size() - 1); }

    void insert (int xP) {
        int pos = upper_bound(all(x), xP) - x.begin();
        x.insert(x.begin() + pos, xP);
        jumpTo.insert(jumpTo.begin() + pos, 0);
        step.insert(step.begin() + pos, 0);
        refine(pos);
    }

    void remove (int xP) {
        int pos = lower_bound(all(x), xP) - x.begin();
        x.erase(x.begin() + pos);
        jumpTo.erase(jumpTo.begin() + pos);
        step.erase(step.begin() + pos);
        refine(pos);
    }

    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(int)':
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:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if (pos == x.size()) return {start, 0};
      |             ~~~~^~~~~~~~~~~
elephants.cpp: In function 'void build(const std::vector<int>&)':
elephants.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     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 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2926 ms 2464 KB Output is correct
8 Correct 3957 ms 2768 KB Output is correct
9 Correct 181 ms 5072 KB Output is correct
10 Correct 3865 ms 5968 KB Output is correct
11 Correct 3703 ms 5468 KB Output is correct
12 Correct 1933 ms 4056 KB Output is correct
13 Correct 3869 ms 3516 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2926 ms 2464 KB Output is correct
8 Correct 3957 ms 2768 KB Output is correct
9 Correct 181 ms 5072 KB Output is correct
10 Correct 3865 ms 5968 KB Output is correct
11 Correct 3703 ms 5468 KB Output is correct
12 Correct 1933 ms 4056 KB Output is correct
13 Correct 3869 ms 3516 KB Output is correct
14 Correct 2368 ms 5768 KB Output is correct
15 Correct 266 ms 3436 KB Output is correct
16 Correct 636 ms 4488 KB Output is correct
17 Correct 1190 ms 5060 KB Output is correct
18 Correct 1910 ms 13844 KB Output is correct
19 Correct 1036 ms 5488 KB Output is correct
20 Correct 1035 ms 5428 KB Output is correct
21 Correct 3357 ms 4660 KB Output is correct
22 Correct 8076 ms 5612 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2926 ms 2464 KB Output is correct
8 Correct 3957 ms 2768 KB Output is correct
9 Correct 181 ms 5072 KB Output is correct
10 Correct 3865 ms 5968 KB Output is correct
11 Correct 3703 ms 5468 KB Output is correct
12 Correct 1933 ms 4056 KB Output is correct
13 Correct 3869 ms 3516 KB Output is correct
14 Correct 2368 ms 5768 KB Output is correct
15 Correct 266 ms 3436 KB Output is correct
16 Correct 636 ms 4488 KB Output is correct
17 Correct 1190 ms 5060 KB Output is correct
18 Correct 1910 ms 13844 KB Output is correct
19 Correct 1036 ms 5488 KB Output is correct
20 Correct 1035 ms 5428 KB Output is correct
21 Correct 3357 ms 4660 KB Output is correct
22 Correct 8076 ms 5612 KB Output is correct
23 Correct 1215 ms 14680 KB Output is correct
24 Correct 1282 ms 9640 KB Output is correct
25 Correct 894 ms 16544 KB Output is correct
26 Execution timed out 9026 ms 10928 KB Time limit exceeded
27 Halted 0 ms 0 KB -