oj.uz

Submission #391728

# Submission time Handle Problem Language Result Execution time Memory
391728 2021-04-19T15:40:51 Z iANikzad Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5827 ms 17416 KB 
#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 init(int _n, int _k, int X[])
{
    n = _n, k = _k;
    for(int i = 0; i < n; i++) ++mp[pos[i] = X[i]];
}

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 ad)
{
    int ptr = -1;
    while(R[++ptr] < x);

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

    if(!ad) 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);
    }
}

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 309 ms 2692 KB Output is correct
8 Correct 335 ms 2128 KB Output is correct
9 Correct 477 ms 4320 KB Output is correct
10 Correct 474 ms 4436 KB Output is correct
11 Correct 458 ms 4440 KB Output is correct
12 Correct 810 ms 4416 KB Output is correct
13 Correct 480 ms 4440 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 309 ms 2692 KB Output is correct
8 Correct 335 ms 2128 KB Output is correct
9 Correct 477 ms 4320 KB Output is correct
10 Correct 474 ms 4436 KB Output is correct
11 Correct 458 ms 4440 KB Output is correct
12 Correct 810 ms 4416 KB Output is correct
13 Correct 480 ms 4440 KB Output is correct
14 Correct 266 ms 2524 KB Output is correct
15 Correct 545 ms 2752 KB Output is correct
16 Correct 1170 ms 4696 KB Output is correct
17 Correct 1358 ms 6048 KB Output is correct
18 Correct 1603 ms 6112 KB Output is correct
19 Correct 947 ms 6016 KB Output is correct
20 Correct 1573 ms 6008 KB Output is correct
21 Correct 1510 ms 6000 KB Output is correct
22 Correct 890 ms 6020 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 309 ms 2692 KB Output is correct
8 Correct 335 ms 2128 KB Output is correct
9 Correct 477 ms 4320 KB Output is correct
10 Correct 474 ms 4436 KB Output is correct
11 Correct 458 ms 4440 KB Output is correct
12 Correct 810 ms 4416 KB Output is correct
13 Correct 480 ms 4440 KB Output is correct
14 Correct 266 ms 2524 KB Output is correct
15 Correct 545 ms 2752 KB Output is correct
16 Correct 1170 ms 4696 KB Output is correct
17 Correct 1358 ms 6048 KB Output is correct
18 Correct 1603 ms 6112 KB Output is correct
19 Correct 947 ms 6016 KB Output is correct
20 Correct 1573 ms 6008 KB Output is correct
21 Correct 1510 ms 6000 KB Output is correct
22 Correct 890 ms 6020 KB Output is correct
23 Correct 4181 ms 12268 KB Output is correct
24 Correct 4086 ms 17416 KB Output is correct
25 Correct 3377 ms 17296 KB Output is correct
26 Correct 3984 ms 17416 KB Output is correct
27 Correct 4115 ms 17264 KB Output is correct
28 Correct 1366 ms 5544 KB Output is correct
29 Correct 1286 ms 5444 KB Output is correct
30 Correct 1393 ms 5576 KB Output is correct
31 Correct 1281 ms 5536 KB Output is correct
32 Correct 3587 ms 16844 KB Output is correct
33 Correct 1652 ms 16128 KB Output is correct
34 Correct 3714 ms 16960 KB Output is correct
35 Correct 1531 ms 17220 KB Output is correct
36 Correct 79 ms 7620 KB Output is correct
37 Correct 2238 ms 17176 KB Output is correct
38 Correct 3608 ms 16052 KB Output is correct
39 Correct 3397 ms 17116 KB Output is correct
40 Correct 3942 ms 16076 KB Output is correct
41 Correct 5624 ms 16872 KB Output is correct
42 Correct 5827 ms 17088 KB Output is correct