oj.uz

Submission #367676

# Submission time Handle Problem Language Result Execution time Memory
367676 2021-02-17T23:35:58 Z ijxjdjd Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 7204 KB 
using namespace std;

#include "elephants.h"
#include <bits/stdc++.h>
//
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#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 = 500;
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, bool needSort) {
    if (blocks[i].size() == 0) {
        return;
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
    return X[lhs] < X[rhs];
    };
    if (needSort) {
        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, false);
    }
}
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], false);
    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, true);
            break;
        }
    }
    REDO--;
    return getAns();
}

Compilation message

elephants.cpp: In function 'void recalcBlock(int, bool)':
elephants.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         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 1 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 1 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 1 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 4252 ms 1516 KB Output is correct
8 Correct 4312 ms 1644 KB Output is correct
9 Correct 2071 ms 2792 KB Output is correct
10 Correct 2374 ms 2392 KB Output is correct
11 Correct 2362 ms 2392 KB Output is correct
12 Correct 2887 ms 3120 KB Output is correct
13 Correct 2432 ms 2392 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 1 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 4252 ms 1516 KB Output is correct
8 Correct 4312 ms 1644 KB Output is correct
9 Correct 2071 ms 2792 KB Output is correct
10 Correct 2374 ms 2392 KB Output is correct
11 Correct 2362 ms 2392 KB Output is correct
12 Correct 2887 ms 3120 KB Output is correct
13 Correct 2432 ms 2392 KB Output is correct
14 Correct 2212 ms 2064 KB Output is correct
15 Correct 2693 ms 2184 KB Output is correct
16 Correct 3976 ms 3176 KB Output is correct
17 Correct 4535 ms 3956 KB Output is correct
18 Correct 4899 ms 3940 KB Output is correct
19 Correct 8175 ms 3180 KB Output is correct
20 Correct 4541 ms 3796 KB Output is correct
21 Correct 4742 ms 3828 KB Output is correct
22 Correct 4248 ms 3180 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 1 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 4252 ms 1516 KB Output is correct
8 Correct 4312 ms 1644 KB Output is correct
9 Correct 2071 ms 2792 KB Output is correct
10 Correct 2374 ms 2392 KB Output is correct
11 Correct 2362 ms 2392 KB Output is correct
12 Correct 2887 ms 3120 KB Output is correct
13 Correct 2432 ms 2392 KB Output is correct
14 Correct 2212 ms 2064 KB Output is correct
15 Correct 2693 ms 2184 KB Output is correct
16 Correct 3976 ms 3176 KB Output is correct
17 Correct 4535 ms 3956 KB Output is correct
18 Correct 4899 ms 3940 KB Output is correct
19 Correct 8175 ms 3180 KB Output is correct
20 Correct 4541 ms 3796 KB Output is correct
21 Correct 4742 ms 3828 KB Output is correct
22 Correct 4248 ms 3180 KB Output is correct
23 Execution timed out 9033 ms 7204 KB Time limit exceeded
24 Halted 0 ms 0 KB -