Submission #1106341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106341		Zero_OP	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	6720 ms	24660 KiB

elephants

#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];
pair<int, int> id[MAX];
int original[MAX];
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 = 0, cur = -1;
 
    for(int i = 0; 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)
    magic = 1280;
    nBlocks = 0;
 
    iota(original, original + N, 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 debugBlock(int i){
    cout << "block : " << i << '\n';
    for(int x : blocks[i]) cout << x << ' ';
    cout << '\n';
}
 
void debugAllBlock(){
    for(int i = 0; i < nBlocks; ++i){
        debugBlock(i);
    }
}
 
void rebuild(){
    copy(x, x + N, tmp);
    sort(tmp, tmp + N);
 
    nBlocks = 0;
    for(int i = 0; i < N; i += magic, ++nBlocks){
        int j = min(i + magic, N) - 1;
        blocks[nBlocks] = vector<int>(tmp + i, tmp + 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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3