oj.uz

Submission #1118510

# Submission time Handle Problem Language Result Execution time Memory
1118510 2024-11-25T15:28:01 Z _callmelucian Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 14224 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 352 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 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 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 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2952 ms 2388 KB Output is correct
8 Correct 3890 ms 4760 KB Output is correct
9 Correct 198 ms 3744 KB Output is correct
10 Correct 3605 ms 6032 KB Output is correct
11 Correct 3870 ms 3944 KB Output is correct
12 Correct 1871 ms 5932 KB Output is correct
13 Correct 3569 ms 9640 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2952 ms 2388 KB Output is correct
8 Correct 3890 ms 4760 KB Output is correct
9 Correct 198 ms 3744 KB Output is correct
10 Correct 3605 ms 6032 KB Output is correct
11 Correct 3870 ms 3944 KB Output is correct
12 Correct 1871 ms 5932 KB Output is correct
13 Correct 3569 ms 9640 KB Output is correct
14 Correct 2650 ms 3812 KB Output is correct
15 Correct 272 ms 3420 KB Output is correct
16 Correct 560 ms 6608 KB Output is correct
17 Correct 1034 ms 7612 KB Output is correct
18 Correct 1913 ms 4824 KB Output is correct
19 Correct 904 ms 3836 KB Output is correct
20 Correct 1046 ms 7032 KB Output is correct
21 Correct 3229 ms 5368 KB Output is correct
22 Correct 7308 ms 9380 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2952 ms 2388 KB Output is correct
8 Correct 3890 ms 4760 KB Output is correct
9 Correct 198 ms 3744 KB Output is correct
10 Correct 3605 ms 6032 KB Output is correct
11 Correct 3870 ms 3944 KB Output is correct
12 Correct 1871 ms 5932 KB Output is correct
13 Correct 3569 ms 9640 KB Output is correct
14 Correct 2650 ms 3812 KB Output is correct
15 Correct 272 ms 3420 KB Output is correct
16 Correct 560 ms 6608 KB Output is correct
17 Correct 1034 ms 7612 KB Output is correct
18 Correct 1913 ms 4824 KB Output is correct
19 Correct 904 ms 3836 KB Output is correct
20 Correct 1046 ms 7032 KB Output is correct
21 Correct 3229 ms 5368 KB Output is correct
22 Correct 7308 ms 9380 KB Output is correct
23 Correct 1089 ms 13080 KB Output is correct
24 Correct 1109 ms 7576 KB Output is correct
25 Correct 908 ms 14224 KB Output is correct
26 Execution timed out 9049 ms 10900 KB Time limit exceeded
27 Halted 0 ms 0 KB -