oj.uz

Submission #367669

# Submission time Handle Problem Language Result Execution time Memory
367669 2021-02-17T22:38:49 Z ijxjdjd Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 12624 KB 
using namespace std;

#include "elephants.h"
#include <bits/stdc++.h>

#define f first
#define s second
#define all(x) begin(x), end(x)
const int MAXN = 150000;
int N;
int BLOCKSIZE;
int L;
const int K = 400;
int REDO = K;
vector<vector<int>> blocks;
vector<vector<pair<int, int>>> storeBack;
vector<int> permVec;
int X[MAXN];
int blockId[MAXN];


void recalcBlock(int i) {
    if (blocks[i].size() == 0) {
        return;
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
    return X[lhs] < X[rhs];
    };
    sort(all(blocks[i]), comp);
    storeBack[i].resize(blocks[i].size());
    int l = blocks[i].size()-1;
    int r = blocks[i].size()-1;
    while (l >= 0) {
        while (X[blocks[i][l]] + L < X[blocks[i][r]]) {
            r--;
        }
        if (r == blocks[i].size()-1) {
            storeBack[i][l] = {1, X[blocks[i][l]] + L};
        }
        else {
            storeBack[i][l] = storeBack[i][r+1];
            storeBack[i][l].f++;
        }
        l--;
    }
}
void rebuild() {
    for (auto& vec : blocks) {
        vec.clear();
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
        return X[lhs] < X[rhs];
    };
    sort(all(permVec), comp);
    for (int i = 0; i < N; i++) {
        blocks[i/K].push_back(permVec[i]);
        blockId[permVec[i]] = i/K;
    }
    for (int i = 0; i < BLOCKSIZE; i++) {
        recalcBlock(i);
    }
}
int getAns() {
    int next = -1;
    int res = 0;
    for (int i = 0; i < BLOCKSIZE; i++) {
        if (blocks[i].size() > 0 && next < X[blocks[i].back()]) {
            int low = 0;
            int high = blocks[i].size()-1;
            while (low < high) {
                int mid = (low + high)/2;
                if (next < X[blocks[i][mid]]) {
                    high = mid;
                }
                else {
                    low = mid+1;
                }
            }
            res += storeBack[i][high].f;
            next = storeBack[i][high].s;
        }
    }
    return res;
}
void init(int n, int l, int LD[])
{
  N = n;
  L = l;
  for (int i = 0; i < N; i++) {
    permVec.push_back(i);
    X[i] = LD[i];
  }
  BLOCKSIZE = (N-1)/K + 1;
  blocks.resize(BLOCKSIZE, {});
  storeBack.resize(BLOCKSIZE, {});
  rebuild();
}

int update(int i, int y)
{
    if (REDO == 0) {
        rebuild();
        REDO = K;
    }
    X[i] = y;
    blocks[blockId[i]].erase(find(all(blocks[blockId[i]]), i));
    recalcBlock(blockId[i]);
    for (int j = 0; j < BLOCKSIZE; j++) {
        if ((j == BLOCKSIZE - 1) || (blocks[j].size() > 0 && X[blocks[j].back()] >= y)) {
            blocks[j].push_back(i);
            blockId[i] = j;
            recalcBlock(j);
            break;
        }
    }
    REDO--;
    return getAns();
}

Compilation message

elephants.cpp: In function 'void recalcBlock(int)':
elephants.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (r == blocks[i].size()-1) {
      |             ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2058 ms 1772 KB Output is correct
8 Correct 1939 ms 2924 KB Output is correct
9 Correct 1562 ms 4328 KB Output is correct
10 Correct 1741 ms 3964 KB Output is correct
11 Correct 1664 ms 3836 KB Output is correct
12 Correct 2253 ms 4496 KB Output is correct
13 Correct 1789 ms 3688 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2058 ms 1772 KB Output is correct
8 Correct 1939 ms 2924 KB Output is correct
9 Correct 1562 ms 4328 KB Output is correct
10 Correct 1741 ms 3964 KB Output is correct
11 Correct 1664 ms 3836 KB Output is correct
12 Correct 2253 ms 4496 KB Output is correct
13 Correct 1789 ms 3688 KB Output is correct
14 Correct 1422 ms 3492 KB Output is correct
15 Correct 1862 ms 3712 KB Output is correct
16 Correct 3078 ms 4968 KB Output is correct
17 Correct 3685 ms 5996 KB Output is correct
18 Correct 3916 ms 5860 KB Output is correct
19 Correct 5713 ms 5432 KB Output is correct
20 Correct 3651 ms 5912 KB Output is correct
21 Correct 3921 ms 6084 KB Output is correct
22 Correct 3238 ms 4836 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2058 ms 1772 KB Output is correct
8 Correct 1939 ms 2924 KB Output is correct
9 Correct 1562 ms 4328 KB Output is correct
10 Correct 1741 ms 3964 KB Output is correct
11 Correct 1664 ms 3836 KB Output is correct
12 Correct 2253 ms 4496 KB Output is correct
13 Correct 1789 ms 3688 KB Output is correct
14 Correct 1422 ms 3492 KB Output is correct
15 Correct 1862 ms 3712 KB Output is correct
16 Correct 3078 ms 4968 KB Output is correct
17 Correct 3685 ms 5996 KB Output is correct
18 Correct 3916 ms 5860 KB Output is correct
19 Correct 5713 ms 5432 KB Output is correct
20 Correct 3651 ms 5912 KB Output is correct
21 Correct 3921 ms 6084 KB Output is correct
22 Correct 3238 ms 4836 KB Output is correct
23 Correct 8161 ms 12624 KB Output is correct
24 Correct 8481 ms 12384 KB Output is correct
25 Correct 7425 ms 12040 KB Output is correct
26 Execution timed out 9076 ms 11488 KB Time limit exceeded
27 Halted 0 ms 0 KB -