oj.uz

Submission #1118503

# Submission time Handle Problem Language Result Execution time Memory
1118503 2024-11-25T15:12:49 Z _callmelucian Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 18480 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 = 800, 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 2 ms 8540 KB Output is correct
2 Correct 1 ms 4444 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 2 ms 8540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 5948 ms 2476 KB Output is correct
8 Correct 7846 ms 10296 KB Output is correct
9 Correct 367 ms 3880 KB Output is correct
10 Correct 3540 ms 4012 KB Output is correct
11 Correct 3840 ms 4012 KB Output is correct
12 Correct 3594 ms 13512 KB Output is correct
13 Correct 3373 ms 3728 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 5948 ms 2476 KB Output is correct
8 Correct 7846 ms 10296 KB Output is correct
9 Correct 367 ms 3880 KB Output is correct
10 Correct 3540 ms 4012 KB Output is correct
11 Correct 3840 ms 4012 KB Output is correct
12 Correct 3594 ms 13512 KB Output is correct
13 Correct 3373 ms 3728 KB Output is correct
14 Correct 4762 ms 11076 KB Output is correct
15 Correct 400 ms 5220 KB Output is correct
16 Correct 976 ms 4716 KB Output is correct
17 Correct 1940 ms 14776 KB Output is correct
18 Correct 3532 ms 4968 KB Output is correct
19 Correct 7427 ms 5972 KB Output is correct
20 Correct 2009 ms 5860 KB Output is correct
21 Correct 6383 ms 5340 KB Output is correct
22 Correct 7352 ms 5536 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 5948 ms 2476 KB Output is correct
8 Correct 7846 ms 10296 KB Output is correct
9 Correct 367 ms 3880 KB Output is correct
10 Correct 3540 ms 4012 KB Output is correct
11 Correct 3840 ms 4012 KB Output is correct
12 Correct 3594 ms 13512 KB Output is correct
13 Correct 3373 ms 3728 KB Output is correct
14 Correct 4762 ms 11076 KB Output is correct
15 Correct 400 ms 5220 KB Output is correct
16 Correct 976 ms 4716 KB Output is correct
17 Correct 1940 ms 14776 KB Output is correct
18 Correct 3532 ms 4968 KB Output is correct
19 Correct 7427 ms 5972 KB Output is correct
20 Correct 2009 ms 5860 KB Output is correct
21 Correct 6383 ms 5340 KB Output is correct
22 Correct 7352 ms 5536 KB Output is correct
23 Correct 1703 ms 11020 KB Output is correct
24 Correct 1737 ms 11308 KB Output is correct
25 Correct 1069 ms 18272 KB Output is correct
26 Execution timed out 9022 ms 18480 KB Time limit exceeded
27 Halted 0 ms 0 KB -