Submission #1179286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179286		InvMOD	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2082 ms	7584 KiB

elephants

#include<bits/stdc++.h>

using namespace std;

//#define name "InvMOD"

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

const int N = 15e4 + 5;
const int B = 300;

int n, L, a[N];

vector<vector<int>> item_block;
vector<vector<pair<int,int>>> dp;

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

        if(j == sz(item) - 1){
            cur_dp[i] = make_pair(item[i] + L, 1);
        }
        else{
            cur_dp[i] = cur_dp[j + 1];
            cur_dp[i].second++;
        }
    }
}

void add(int curBlock, int target){
    item_block[curBlock].push_back(target);
    sort(all(item_block[curBlock]));

    if(sz(item_block[curBlock]) == 2 * B){
        vector<int> nBlock(item_block[curBlock].begin() + B, item_block[curBlock].end());
        item_block[curBlock].resize(B);
        dp[curBlock].resize(B);
        item_block.insert(item_block.begin() + curBlock + 1, nBlock);
        dp.insert(dp.begin() + curBlock + 1, vector<pair<int,int>>(B));
        calc_dp(item_block[curBlock], dp[curBlock]), calc_dp(item_block[curBlock + 1], dp[curBlock + 1]);
    }
    else{
        dp[curBlock].resize(sz(item_block[curBlock]));
        calc_dp(item_block[curBlock], dp[curBlock]);
    }
}

void rem(int curBlock, int target){
    item_block[curBlock].erase(find(all(item_block[curBlock]), target));
    if(!sz(item_block[curBlock])){
        item_block.erase(item_block.begin() + curBlock);
        dp.erase(dp.begin() + curBlock);
    }
    else{
        dp[curBlock].resize(sz(item_block[curBlock]));
        calc_dp(item_block[curBlock], dp[curBlock]);
    }
}

int find_answer(){
    int nxt_pos = -1, answer = 0;
    for(int curblock = 0; curblock < sz(item_block); curblock++){
        if(item_block[curblock].back() <= nxt_pos) continue;
        int p = upper_bound(all(item_block[curblock]), nxt_pos) - item_block[curblock].begin();
        nxt_pos = dp[curblock][p].first;
        answer = answer + dp[curblock][p].second;
    }
    return answer;
}

int find_block(int val){
    int l = 0, r = sz(item_block);
    while(l + 1 < r){
        int m = l+r>>1;
        if(item_block[m][0] > val){
            r = m;
        }
        else l = m;
    }
    return l;
}

int update(int ii, int nval){
    rem(find_block(a[ii]), a[ii]);
    a[ii] = nval;
    add(find_block(a[ii]), a[ii]);
    return find_answer();
}

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

    vector<int> idx(n); iota(all(idx), 0);
    sort(all(idx), [&](int x, int y){return a[x] < a[y];});

    for(int i = 0; i < n; i += B){
        vector<int> item;
        for(int j = i; j < min(n, i + B); j++){
            item.push_back(a[idx[j]]);
        }
        item_block.push_back(item);
        dp.push_back(vector<pair<int,int>>(B));
        calc_dp(item_block[i / B], dp[i / B]);
    }
}

#ifdef name
    int32_t main()
    {
        freopen(name".INP", "r", stdin);
        freopen(name".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 p,val; cin >> p >> val;

            cout << update(p, val) << "\n";
        }
    }
#endif // name

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