Submission #391725

#	Time	Username	Problem	Language	Result	Execution time	Memory
391725		iANikzad	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	2 ms	648 KiB

elephants

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 1.5e5 + 7;
const int mod = 1e9 + 7;
const int INF = 2e9 + 7;
const int mlog = 20;
const int SQRT = 400;

int n, k;

int bcnt;
int R[SQRT + 7];

int pos[maxn];

map<int, int> mp;
vector<int> jump[SQRT + 7], cnt[SQRT + 7], bucket[SQRT + 7];

void solve(int ind)
{
    jump[ind] = vector<int>(bucket[ind].size());
    cnt[ind] = vector<int>(bucket[ind].size());

    for(int i = bucket[ind].size() - 1, j = bucket[ind].size(); ~i; i--)
    {
        while(bucket[ind][j - 1] > bucket[ind][i] + k)
            j--;

        if(j < (int)bucket[ind].size()) jump[ind][i] = jump[ind][j], cnt[ind][i] = cnt[ind][j] + 1;
        else jump[ind][i] = bucket[ind][i] + k, cnt[ind][i] = 1;
    }
}

void add(int x, bool rmv)
{
    int ptr = -1;
    while(R[++ptr] < x);

    int ind = lower_bound(bucket[ptr].begin(), bucket[ptr].end(), x) - bucket[ptr].begin();

    if(rmv) bucket[ptr].erase(bucket[ptr].begin() + ind);
    else  bucket[ptr].insert(bucket[ptr].begin() + ind, x);

    solve(ptr);
}

void REBUILD()
{
    bcnt = 0;
    for(pii p : mp)
    {
        if(!bcnt || bucket[bcnt - 1].size() >= SQRT)
            bucket[bcnt++].clear();

        bucket[bcnt - 1].pb(p.F);
    }

    for(int i = 0; i < bcnt; i++)
    {
        if(i < bcnt - 1) R[i] = bucket[i + 1][0] - 1;
        else R[i] = +INF;

        solve(i);
    }
}

void init(int _n, int _k, int X[])
{
    n = _n, k = _k;
    for(int i = 0; i < n; i++) ++mp[pos[i] = X[i]];
}

int cntBLOCK;
int update(int i,int y)
{
    if(cntBLOCK++ % SQRT == 0)
        REBUILD();

    if(!--mp[pos[i]]) add(pos[i], 0), mp.erase(pos[i]);
    if(!mp[y]) add(y, 1);
    mp[y]++, pos[i] = y;

    int ans = 0, cur = -1;
    for(int i = 0; i < bcnt; i++)
    {
        int ind = upper_bound(bucket[i].begin(), bucket[i].end(), cur) - bucket[i].begin();
        if(ind < (int)bucket[i].size())
            ans += cnt[i][ind], cur = jump[i][ind];
    }

    return ans;
}

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