Submission #941632

#	Time	Username	Problem	Language	Result	Execution time	Memory
941632		Nhoksocqt1	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	5054 ms	26052 KiB

elephants

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 150005;
const int BLOCK = 390;

ii sorted_pos[MAXN], bel[MAXN];
int id[BLOCK][2 * BLOCK], dp[BLOCK][2 * BLOCK];
int pos_block[BLOCK][2 * BLOCK], nxt[BLOCK][2 * BLOCK];
int pos[MAXN], block_size[MAXN], nArr, numBlock, maxLen;


void build(void) {
    for (int i = 0; i < nArr; ++i)
        sorted_pos[i] = ii(pos[i], i);

    sort(sorted_pos, sorted_pos + nArr);

    numBlock = (nArr + BLOCK - 1) / BLOCK;
    for (int i = 0; i < numBlock; ++i) {
        block_size[i] = min(nArr, (i + 1) * BLOCK) - i * BLOCK;

        int k(block_size[i] - 1);
        for (int j = k; j >= 0; --j) {
            pos_block[i][j] = sorted_pos[i * BLOCK + j].fi;
            while(j < k && pos_block[i][j] + maxLen < pos_block[i][k - 1])
                --k;

            id[i][j] = sorted_pos[i * BLOCK + j].se;
            bel[sorted_pos[i * BLOCK + j].se] = {i, j};
            if(pos_block[i][j] + maxLen >= pos_block[i][block_size[i] - 1]) {
                nxt[i][j] = pos_block[i][j] + maxLen;
                dp[i][j] = 1;
            } else {
                nxt[i][j] = nxt[i][k];
                dp[i][j] = 1 + dp[i][k];
            }
        }
    }
}

void rebuildBlock(int i) {
    int k(block_size[i] - 1);
    for (int j = k; j >= 0; --j) {
        while(j + 1 < k && pos_block[i][j] + maxLen < pos_block[i][k - 1])
            --k;

        if(pos_block[i][j] + maxLen >= pos_block[i][block_size[i] - 1]) {
            nxt[i][j] = pos_block[i][j] + maxLen;
            dp[i][j] = 1;
        } else {
            nxt[i][j] = nxt[i][k];
            dp[i][j] = 1 + dp[i][k];
        }
    }
}

int query(void) {
    int res(0), lst(-1);
    for (int i = 0; i < numBlock; ++i) {
        int p = upper_bound(pos_block[i], pos_block[i] + block_size[i], lst) - pos_block[i];
        if(p < block_size[i]) {
            res += dp[i][p];
            lst = nxt[i][p];
        }
    }

    return res;
}

int update(int u, int newPos) {
    pos[u] = newPos;

    ii x(bel[u]);
    /*for (int j = 0; j < block_size[x.fi]; ++j)
        cout << pos_block[x.fi][j] << ' '; cout << '\n';

    for (int j = 0; j < block_size[x.fi]; ++j)
        cout << id[x.fi][j] << ' '; cout << '\n';

    for (int j = 0; j < block_size[x.fi]; ++j)
        cout << bel[id[x.fi][j]].se << ' '; cout << '\n';*/

    for (int i = x.se + 1; i < block_size[x.fi]; ++i) {
        pos_block[x.fi][i - 1] = pos_block[x.fi][i];
        id[x.fi][i - 1] = id[x.fi][i];
        --bel[id[x.fi][i - 1]].se;
    }

    --block_size[x.fi];
    rebuildBlock(x.fi);

    ii y = ii(numBlock - 1, block_size[numBlock - 1]);
    for (int i = 0; i < numBlock; ++i) {
        if(newPos <= pos_block[i][block_size[i] - 1]) {
            int j = upper_bound(pos_block[i], pos_block[i] + block_size[i], newPos) - pos_block[i];
            y = {i, j};
            break;
        }
    }

    assert(y.fi >= 0);
    for (int i = block_size[y.fi]; i > y.se; --i) {
        pos_block[y.fi][i] = pos_block[y.fi][i - 1];
        id[y.fi][i] = id[y.fi][i - 1];
        ++bel[id[y.fi][i]].se;
    }

    ++block_size[y.fi];
    pos_block[y.fi][y.se] = newPos;
    bel[u] = ii(y.fi, y.se);
    id[y.fi][y.se] = u;
    /*cout << y.fi << ' ' << y.se << ": ";
    for (int j = 0; j < block_size[y.fi]; ++j)
        cout << pos_block[x.fi][j] << ' '; cout << '\n';

    for (int j = 0; j < block_size[y.fi]; ++j)
        cout << id[x.fi][j] << ' '; cout << '\n';

    for (int j = 0; j < block_size[y.fi]; ++j)
        cout << bel[id[x.fi][j]].se << ' '; cout << '\n';*/

    rebuildBlock(y.fi);
    if(block_size[x.fi] == 0 || block_size[y.fi] >= 2 * BLOCK)
        build();

    return query();
}

void init(int _N, int _L, int _X[]) {
    nArr = _N, maxLen = _L;
    for (int i = 0; i < nArr; ++i)
        pos[i] = _X[i];

    build();
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "ioi11_elephants"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int *X, n, L;
    cin >> n >> L;
    X = new int[n + 1];
    for (int i = 0; i < n; ++i)
        cin >> X[i];

    init(n, L, X);

    int q;
    cin >> q;
    for (int t = 0; t < q; ++t) {
        int i, y;
        cin >> i >> y;
        cout << update(i, y) << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

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