oj.uz

Submission #367677

# Submission time Handle Problem Language Result Execution time Memory
367677 2021-02-17T23:36:24 Z ijxjdjd Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 7680 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 = 600;
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 2410 ms 1516 KB Output is correct
8 Correct 3014 ms 1772 KB Output is correct
9 Correct 1631 ms 2920 KB Output is correct
10 Correct 1066 ms 2536 KB Output is correct
11 Correct 1078 ms 2408 KB Output is correct
12 Correct 2349 ms 2980 KB Output is correct
13 Correct 1106 ms 2536 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 2410 ms 1516 KB Output is correct
8 Correct 3014 ms 1772 KB Output is correct
9 Correct 1631 ms 2920 KB Output is correct
10 Correct 1066 ms 2536 KB Output is correct
11 Correct 1078 ms 2408 KB Output is correct
12 Correct 2349 ms 2980 KB Output is correct
13 Correct 1106 ms 2536 KB Output is correct
14 Correct 1733 ms 2096 KB Output is correct
15 Correct 2194 ms 2064 KB Output is correct
16 Correct 3394 ms 3048 KB Output is correct
17 Correct 3707 ms 3920 KB Output is correct
18 Correct 3860 ms 3812 KB Output is correct
19 Correct 6786 ms 3300 KB Output is correct
20 Correct 3729 ms 3812 KB Output is correct
21 Correct 3815 ms 3860 KB Output is correct
22 Correct 2226 ms 3300 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 2410 ms 1516 KB Output is correct
8 Correct 3014 ms 1772 KB Output is correct
9 Correct 1631 ms 2920 KB Output is correct
10 Correct 1066 ms 2536 KB Output is correct
11 Correct 1078 ms 2408 KB Output is correct
12 Correct 2349 ms 2980 KB Output is correct
13 Correct 1106 ms 2536 KB Output is correct
14 Correct 1733 ms 2096 KB Output is correct
15 Correct 2194 ms 2064 KB Output is correct
16 Correct 3394 ms 3048 KB Output is correct
17 Correct 3707 ms 3920 KB Output is correct
18 Correct 3860 ms 3812 KB Output is correct
19 Correct 6786 ms 3300 KB Output is correct
20 Correct 3729 ms 3812 KB Output is correct
21 Correct 3815 ms 3860 KB Output is correct
22 Correct 2226 ms 3300 KB Output is correct
23 Correct 7226 ms 7512 KB Output is correct
24 Correct 7663 ms 7680 KB Output is correct
25 Correct 6594 ms 7304 KB Output is correct
26 Execution timed out 9073 ms 6624 KB Time limit exceeded
27 Halted 0 ms 0 KB -