oj.uz

Submission #1118516

# Submission time Handle Problem Language Result Execution time Memory
1118516 2024-11-25T15:36:40 Z _callmelucian Dancing Elephants (IOI11_elephants) C++14
26 / 100
 13 ms 1292 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);
    }

    void batchJump (int &start, int &ans) {
        if (x[0] > start) return start = jumpTo[0], ans += step[0], void();
        int pos = 0;
        for (int mask = 1 << 9; mask; mask >>= 1) {
            if ((pos | mask) >= x.size()) continue;
            if (x[pos | mask] <= start) pos |= mask;
        }
        pos++;
        if (pos < x.size()) start = jumpTo[pos], ans += 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) cur.batchJump(curPos, ans);
    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 'void block::batchJump(int&, int&)':
elephants.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if ((pos | mask) >= x.size()) continue;
      |                 ~~~~~~~~~~~~~^~~~~~~~~~~
elephants.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (pos < x.size()) start = jumpTo[pos], ans += step[pos];
      |             ~~~~^~~~~~~~~~
elephants.cpp: In function 'void build(const std::vector<int>&)':
elephants.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     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 348 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 348 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 1 ms 504 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1 ms 504 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 13 ms 1292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1 ms 504 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 13 ms 1292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 1 ms 504 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 13 ms 1292 KB Output isn't correct
8 Halted 0 ms 0 KB -