oj.uz

Submission #1118492

# Submission time Handle Problem Language Result Execution time Memory
1118492 2024-11-25T14:55:17 Z _callmelucian Dancing Elephants (IOI11_elephants) C++14
0 / 100
 1 ms 340 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 = 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();
}

#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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -