oj.uz

Submission #1106333

# Submission time Handle Problem Language Result Execution time Memory
1106333 2024-10-30T02:18:34 Z Zero_OP Dancing Elephants (IOI11_elephants) C++14
26 / 100
 124 ms 13128 KB 
#include <bits/stdc++.h>

#ifndef LOCAL
    #include "elephants.h"
#endif // LOCAL

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()

using namespace std;

const int MAX = 150000;
int magic = sqrt(MAX) + 10;
const int maxMagic = 500;

int N, L, x[MAX], tmp[MAX], nBlocks, countUpdates = 0;
vector<int> blocks[maxMagic];
vector<pair<int, int>> infoBlocks[MAX]; //[n_jumps, last_jump]

void buildBlock(int ib){
    infoBlocks[ib].resize(sz(blocks[ib]));
    for(int i = sz(blocks[ib]) - 1; i >= 0; --i){
        if(i == sz(blocks[ib]) - 1){
            infoBlocks[ib][i] = {1, blocks[ib][i] + L};
        } else{
            int l = i + 1, r = sz(blocks[ib]) - 1;
            int n_jumps = 1, last_jump = blocks[ib][i] + L;
            while(l <= r){
                int mid = l + r >> 1;
                if(blocks[ib][i] + L < blocks[ib][mid]){
                    n_jumps = infoBlocks[ib][mid].first + 1;
                    last_jump = infoBlocks[ib][mid].second;
                    r = mid - 1;
                } else l = mid + 1;
            }

            infoBlocks[ib][i] = {n_jumps, last_jump};
        }
    }
}

int simulate(){
    int total, cur;
    tie(total, cur) = infoBlocks[0][0];

    for(int i = 1; i < nBlocks; ++i){
        if(blocks[i].empty() || blocks[i].back() <= cur) continue; //over

        int pos = upper_bound(all(blocks[i]), cur) - blocks[i].begin();
        total += infoBlocks[i][pos].first;
        cur = infoBlocks[i][pos].second;
    }

    return total;
}

void init(int _N, int _L, int _X[]){
    N = _N;
    L = _L;
    for(int i = 0; i < N; ++i) x[i] = _X[i];

    //tested for magic exactly sqrt(n)
    nBlocks = 0;

    for(int i = 0; i < N; i += magic, ++nBlocks){
        int j = min(i + magic, N) - 1;
        blocks[nBlocks] = vector<int>(x + i, x + j + 1);
        buildBlock(nBlocks);
    }
}

void rebuild(){
    int sz = 0;
    for(int i = 0; i < nBlocks; ++i){
        for(int j : blocks[i]){
            x[sz++] = j;
        }

        blocks[i].clear();
    }

    nBlocks = 0;
    for(int i = 0; i < N; i += magic, ++nBlocks){
        int j = min(i + magic, N) - 1;
        blocks[nBlocks] = vector<int>(x + i, x + j + 1);
        buildBlock(nBlocks);
    }
}

void remove(int x){
    for(int i = 0; i < nBlocks; ++i){
        if(blocks[i].empty()) continue;
        if(!binary_search(all(blocks[i]), x)) continue;
        blocks[i].erase(find(all(blocks[i]), x));
        buildBlock(i);
        return;
    }

    assert(false);
}

void insert(int x){
    for(int i = 0; i < nBlocks; ++i){
        if(blocks[i].empty()) continue;
        if(blocks[i].back() > x){
            int pos = upper_bound(all(blocks[i]), x) - blocks[i].begin();
            blocks[i].insert(blocks[i].begin() + pos, x);
            buildBlock(i);
            return;
        }
    }

    blocks[nBlocks - 1].push_back(x);
    buildBlock(nBlocks - 1);
}

int update(int i, int y){
    ++countUpdates;

    if(countUpdates == 2 * magic){
        x[i] = y;
        rebuild();
        countUpdates = 0;
    }

    remove(x[i]);
    x[i] = y;
    insert(x[i]);

    return simulate();
}

#ifdef LOCAL
    int main(){
        ios_base::sync_with_stdio(0); cin.tie(0);

        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);

        int N, L;
        cin >> N >> L;
        int X[N];
        for(int i = 0; i < N; ++i) cin >> X[i];

        init(N, L, X);
        int Q; cin >> Q;
        while(Q--){
            int i, y;
            cin >> i >> y;
            cout << update(i, y) << '\n';
        }

        return 0;
    }
#endif // LOCAL

Compilation message

elephants.cpp: In function 'void buildBlock(int)':
elephants.cpp:30:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |                 int mid = l + r >> 1;
      |                           ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12880 KB Output is correct
2 Correct 2 ms 12880 KB Output is correct
3 Correct 2 ms 12880 KB Output is correct
4 Correct 2 ms 12880 KB Output is correct
5 Correct 2 ms 12880 KB Output is correct
6 Correct 2 ms 12880 KB Output is correct
7 Incorrect 124 ms 13128 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12880 KB Output is correct
2 Correct 2 ms 12880 KB Output is correct
3 Correct 2 ms 12880 KB Output is correct
4 Correct 2 ms 12880 KB Output is correct
5 Correct 2 ms 12880 KB Output is correct
6 Correct 2 ms 12880 KB Output is correct
7 Incorrect 124 ms 13128 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12880 KB Output is correct
2 Correct 2 ms 12880 KB Output is correct
3 Correct 2 ms 12880 KB Output is correct
4 Correct 2 ms 12880 KB Output is correct
5 Correct 2 ms 12880 KB Output is correct
6 Correct 2 ms 12880 KB Output is correct
7 Incorrect 124 ms 13128 KB Output isn't correct
8 Halted 0 ms 0 KB -