Submission #1177724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177724		InvMOD	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	5323 ms	6568 KiB

elephants

#include<bits/stdc++.h>

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define dbg(x) "[" << #x " = " << (x) << "]"

using namespace std;

const int N = 15e4 + 5;
const int B = 400;
const int NBlock = (N + B - 1) / B;

int n, L, a[N], idBlock[N], dp[N], lp[N];

int LBlock[NBlock], RBlock[NBlock];

vector<int> item_block[NBlock];

void calc_dp(vector<int>& item){
    for(int i = sz(item) - 1, j = i; i >= 0; i--){
        while(a[item[i]] + L < a[item[j]]) j--;

        if(j == sz(item) - 1){
            int u = item[i];
            lp[u] = a[u] + L;
            dp[u] = 1;
        }
        else{
            int u = item[i], v = item[j + 1];
            lp[u] = lp[v];
            dp[u] = dp[v] + 1;
        }
    }
}

void updateBlock(int curblock, int op, int target){
    if(op == 1){
        // add
        item_block[curblock].push_back(target);
        sort(all(item_block[curblock]), [&](int x, int y){
                return a[x] < a[y];
        });
    }
    else{
        // remove
        for(int i = 0; i < sz(item_block[curblock]); i++){
            if(item_block[curblock][i] == target){
                item_block[curblock].erase(item_block[curblock].begin() + i);
                break;
            }
        }
    }
    if(sz(item_block[curblock])){
        LBlock[curblock] = a[item_block[curblock][0]];
        RBlock[curblock] = a[item_block[curblock].back()];
    }

    calc_dp(item_block[curblock]);
    return;
}

void build()
{
    vector<int> idx(n + 1);
    iota(1 + all(idx), 1);

    sort(1 + all(idx), [&](int x, int y){
        return a[x] < a[y];
    });

    int nblock = (n + B - 1) / B;
    for(int i = 1; i <= nblock; i++){
        item_block[i].clear();
        int blockL = (i - 1) * B + 1;
        int blockR = min(n, i * B);

        LBlock[i] = a[idx[blockL]];
        RBlock[i] = a[idx[blockR]];

        for(int j = blockL; j <= blockR; j++){
            idBlock[idx[j]] = i;
            item_block[i].push_back(idx[j]);
        }
        calc_dp(item_block[i]);
    }
    //cerr << "DONE BUILD\n";
}

int find_answer(){
    int nxt_pos = -1, answer = 0, mxBlockSz = 0;
    for(int curblock = 1; curblock <= (n + B - 1) / B; curblock++){
        mxBlockSz = max(mxBlockSz, sz(item_block[curblock]));
        if(!sz(item_block[curblock])) continue;
        if(a[item_block[curblock].back()] <= nxt_pos) continue;
        
        int l = -1, r = sz(item_block[curblock]);
        while(l + 1 < r){
            int m = l+r>>1;
            if(a[item_block[curblock][m]] > nxt_pos){
                r = m;
            }
            else l = m;
        }

        if(r == sz(item_block[curblock])){
            continue;
        }
        else{
            int v = item_block[curblock][r];
            answer += dp[v];
            nxt_pos = lp[v];
            //cout << dbg(dp[v]) << dbg(lp[v]) << "\n";
        }
    }

    if(mxBlockSz >= B * 2) build();
    return answer;
}

int update(int ii, int nval)
{
    ++ii;
    updateBlock(idBlock[ii], -1, ii);
    //cerr << "DONE UPDATE BLOCK: " << idBlock[ii] <<" " << nval << "\n";

    int l = 1, r = (n + B - 1) / B + 1;
    while(l + 1 < r){
        int m = l+r>>1;

        if(LBlock[m] <= nval){
            l = m;
        }
        else r = m;
    }
    idBlock[ii] = l;

    a[ii] = nval;
    updateBlock(idBlock[ii], +1, ii);
    //cerr << "DONE UPDATE BLOCK: " << idBlock[ii] <<" " << nval << "\n";

    return find_answer();
}

void init(int N, int Li, int X[])
{
    for(int i = 1; i <= N; i++){
        a[i] = X[i - 1];
    }
    n = N, L = Li; build();
}

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