oj.uz

답안 #1118505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1118505 2024-11-25T15:19:02 Z _callmelucian 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 18532 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 = 1000, 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: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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8652 KB Output is correct
2 Correct 2 ms 8664 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8652 KB Output is correct
2 Correct 2 ms 8664 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8652 KB Output is correct
2 Correct 2 ms 8664 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 6164 ms 10020 KB Output is correct
8 Correct 8550 ms 2828 KB Output is correct
9 Correct 358 ms 7564 KB Output is correct
10 Correct 3783 ms 4224 KB Output is correct
11 Correct 3741 ms 11620 KB Output is correct
12 Correct 4011 ms 3948 KB Output is correct
13 Correct 3770 ms 13388 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8652 KB Output is correct
2 Correct 2 ms 8664 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 6164 ms 10020 KB Output is correct
8 Correct 8550 ms 2828 KB Output is correct
9 Correct 358 ms 7564 KB Output is correct
10 Correct 3783 ms 4224 KB Output is correct
11 Correct 3741 ms 11620 KB Output is correct
12 Correct 4011 ms 3948 KB Output is correct
13 Correct 3770 ms 13388 KB Output is correct
14 Correct 4870 ms 3820 KB Output is correct
15 Correct 479 ms 3444 KB Output is correct
16 Correct 1232 ms 4740 KB Output is correct
17 Correct 2206 ms 5832 KB Output is correct
18 Correct 3975 ms 5072 KB Output is correct
19 Correct 7460 ms 15368 KB Output is correct
20 Correct 2255 ms 14948 KB Output is correct
21 Correct 6871 ms 14356 KB Output is correct
22 Correct 7040 ms 9340 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8652 KB Output is correct
2 Correct 2 ms 8664 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 6164 ms 10020 KB Output is correct
8 Correct 8550 ms 2828 KB Output is correct
9 Correct 358 ms 7564 KB Output is correct
10 Correct 3783 ms 4224 KB Output is correct
11 Correct 3741 ms 11620 KB Output is correct
12 Correct 4011 ms 3948 KB Output is correct
13 Correct 3770 ms 13388 KB Output is correct
14 Correct 4870 ms 3820 KB Output is correct
15 Correct 479 ms 3444 KB Output is correct
16 Correct 1232 ms 4740 KB Output is correct
17 Correct 2206 ms 5832 KB Output is correct
18 Correct 3975 ms 5072 KB Output is correct
19 Correct 7460 ms 15368 KB Output is correct
20 Correct 2255 ms 14948 KB Output is correct
21 Correct 6871 ms 14356 KB Output is correct
22 Correct 7040 ms 9340 KB Output is correct
23 Correct 1712 ms 11052 KB Output is correct
24 Correct 2008 ms 11308 KB Output is correct
25 Correct 1435 ms 10892 KB Output is correct
26 Execution timed out 9022 ms 18532 KB Time limit exceeded
27 Halted 0 ms 0 KB -