oj.uz

Submission #291112

# Submission time Handle Problem Language Result Execution time Memory
291112 2020-09-04T16:57:40 Z Kastanda Dancing Elephants (IOI11_elephants) C++11
100 / 100
 6372 ms 12772 KB 
// M
#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
const int N = 151234, SQ = 840, QS = N / SQ + 4, SCALE = N * 3;
int n, nsq, lzcnt, EXTRAS, B[N];
ll k, X[N];
vector < ll > V[QS];
vector < pair < int , ll > > dp[QS];
inline void Build(int block)
{
        int sz = (int)V[block].size();
        assert(sz >= 1); // For convenience.

        dp[block].resize(sz);
        int r = sz;
        for (int i = sz - 1; i >= 0; i --)
        {
                while (V[block][r - 1] > V[block][i] + k)
                        r --;
                if (r < sz)
                        dp[block][i] = {dp[block][r].first + 1, dp[block][r].second};
                else
                        dp[block][i] = {1, V[block][i] + k};
        }
}
inline void Erase(int block, ll val)
{
        for (int i = 0; i < (int)V[block].size(); i ++)
                if (V[block][i] == val)
                {
                        V[block].erase(V[block].begin() + i);
                        break;
                }
        Build(block);
}
inline void Insert(int block, ll val)
{
        int i = 0;
        while (i < (int)V[block].size() && V[block][i] < val)
                i ++;
        V[block].insert(V[block].begin() + i, val);
        Build(block);
}
inline void Refresh()
{
        lzcnt = 0;
        vector < int > srt(n, 0);
        for (int i = 0; i < n; i ++)
                srt[i] = i;
        sort(srt.begin(), srt.end(), [&](int i, int j){return X[i] < X[j];});
        for (int i = 0; i < nsq; i ++)
                V[i].clear();
        for (int i = 0; i < n; i ++)
                V[i / SQ].push_back(X[srt[i]]), B[srt[i]] = i / SQ;
        for (int i = 0; i < nsq; i ++)
                Build(i);
}
inline int Calculate()
{
        int Cnt = 0;
        ll nw = -1e18;
        for (int block = 0; block < nsq; block ++)
                if (V[block].size() && V[block].back() > nw)
                {
                        int lb = upper_bound(V[block].begin(), V[block].end(), nw) - V[block].begin();
                        assert(lb < (int)V[block].size());
                        Cnt += dp[block][lb].first;
                        nw = dp[block][lb].second;
                }
        return Cnt - EXTRAS;
}

void init(int _n, int _k, int _X[])
{
        n = _n;
        k = (ll)_k * SCALE + n;
        for (int i = 0; i < n; i ++)
                X[i] = _X[i] * (ll)SCALE + i;
        ll val = (ll)(2e9 + 9);
        while (n % SQ != 0)
                X[n] = val * SCALE + n, n ++, val += (ll)(1e9 + 9), EXTRAS ++;
        for (int i = 0; i < n; i ++)
                V[i / SQ].push_back(X[i]), B[i] = i / SQ;
        assert(n % SQ == 0);
        nsq = n / SQ;
        for (int i = 0; i < nsq; i ++)
                Build(i);
}

int update(int i, int y)
{
        lzcnt ++;
        if (lzcnt + 3 >= SQ)
                Refresh();

        // If some stuff, refresh the data structure ...

        ll val = y * (ll)SCALE + i;

        // Removing the i-th element from it's block
        {
                int block = B[i];
                Erase(block, X[i]);
        }

        // Adding the i-th element to it's new block
        {
                int block = 0;
                for (; block < nsq; block ++)
                        if (block + 1 == nsq || V[block + 1][0] > val)
                                break;
                if (block == nsq)
                        block --;
                X[i] = val;
                B[i] = block;
                Insert(block, X[i]);
        }

        // Calculating the result :
        return Calculate();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 512 ms 1656 KB Output is correct
8 Correct 535 ms 2168 KB Output is correct
9 Correct 513 ms 4004 KB Output is correct
10 Correct 717 ms 3296 KB Output is correct
11 Correct 735 ms 3248 KB Output is correct
12 Correct 1088 ms 4308 KB Output is correct
13 Correct 713 ms 3248 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 512 ms 1656 KB Output is correct
8 Correct 535 ms 2168 KB Output is correct
9 Correct 513 ms 4004 KB Output is correct
10 Correct 717 ms 3296 KB Output is correct
11 Correct 735 ms 3248 KB Output is correct
12 Correct 1088 ms 4308 KB Output is correct
13 Correct 713 ms 3248 KB Output is correct
14 Correct 648 ms 2296 KB Output is correct
15 Correct 799 ms 2776 KB Output is correct
16 Correct 1872 ms 4016 KB Output is correct
17 Correct 1913 ms 5456 KB Output is correct
18 Correct 2031 ms 5592 KB Output is correct
19 Correct 1152 ms 4440 KB Output is correct
20 Correct 1902 ms 5516 KB Output is correct
21 Correct 1823 ms 5716 KB Output is correct
22 Correct 1250 ms 4344 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 512 ms 1656 KB Output is correct
8 Correct 535 ms 2168 KB Output is correct
9 Correct 513 ms 4004 KB Output is correct
10 Correct 717 ms 3296 KB Output is correct
11 Correct 735 ms 3248 KB Output is correct
12 Correct 1088 ms 4308 KB Output is correct
13 Correct 713 ms 3248 KB Output is correct
14 Correct 648 ms 2296 KB Output is correct
15 Correct 799 ms 2776 KB Output is correct
16 Correct 1872 ms 4016 KB Output is correct
17 Correct 1913 ms 5456 KB Output is correct
18 Correct 2031 ms 5592 KB Output is correct
19 Correct 1152 ms 4440 KB Output is correct
20 Correct 1902 ms 5516 KB Output is correct
21 Correct 1823 ms 5716 KB Output is correct
22 Correct 1250 ms 4344 KB Output is correct
23 Correct 3358 ms 10864 KB Output is correct
24 Correct 4053 ms 11104 KB Output is correct
25 Correct 2588 ms 10396 KB Output is correct
26 Correct 3986 ms 9004 KB Output is correct
27 Correct 4878 ms 8964 KB Output is correct
28 Correct 2611 ms 2560 KB Output is correct
29 Correct 2549 ms 2456 KB Output is correct
30 Correct 2593 ms 2580 KB Output is correct
31 Correct 2526 ms 2456 KB Output is correct
32 Correct 4933 ms 8952 KB Output is correct
33 Correct 4335 ms 9032 KB Output is correct
34 Correct 4619 ms 9044 KB Output is correct
35 Correct 4285 ms 9080 KB Output is correct
36 Correct 1935 ms 10792 KB Output is correct
37 Correct 5339 ms 12772 KB Output is correct
38 Correct 4672 ms 8992 KB Output is correct
39 Correct 4518 ms 8956 KB Output is correct
40 Correct 4813 ms 8992 KB Output is correct
41 Correct 6278 ms 10916 KB Output is correct
42 Correct 6372 ms 10784 KB Output is correct