oj.uz

Submission #291106

# Submission time Handle Problem Language Result Execution time Memory
291106 2020-09-04T16:52:19 Z Kastanda Dancing Elephants (IOI11_elephants) C++11
100 / 100
 8939 ms 17540 KB 
// M
#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
const int N = 151234, SQ = 400, 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 2 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 2 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 1 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 2 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 1 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 275 ms 1784 KB Output is correct
8 Correct 298 ms 2040 KB Output is correct
9 Correct 495 ms 3624 KB Output is correct
10 Correct 736 ms 3288 KB Output is correct
11 Correct 674 ms 3288 KB Output is correct
12 Correct 1096 ms 4072 KB Output is correct
13 Correct 737 ms 3368 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 275 ms 1784 KB Output is correct
8 Correct 298 ms 2040 KB Output is correct
9 Correct 495 ms 3624 KB Output is correct
10 Correct 736 ms 3288 KB Output is correct
11 Correct 674 ms 3288 KB Output is correct
12 Correct 1096 ms 4072 KB Output is correct
13 Correct 737 ms 3368 KB Output is correct
14 Correct 482 ms 2404 KB Output is correct
15 Correct 520 ms 2808 KB Output is correct
16 Correct 1741 ms 4396 KB Output is correct
17 Correct 2175 ms 5736 KB Output is correct
18 Correct 2209 ms 5652 KB Output is correct
19 Correct 1303 ms 4436 KB Output is correct
20 Correct 2005 ms 5720 KB Output is correct
21 Correct 2009 ms 5720 KB Output is correct
22 Correct 1386 ms 4436 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 275 ms 1784 KB Output is correct
8 Correct 298 ms 2040 KB Output is correct
9 Correct 495 ms 3624 KB Output is correct
10 Correct 736 ms 3288 KB Output is correct
11 Correct 674 ms 3288 KB Output is correct
12 Correct 1096 ms 4072 KB Output is correct
13 Correct 737 ms 3368 KB Output is correct
14 Correct 482 ms 2404 KB Output is correct
15 Correct 520 ms 2808 KB Output is correct
16 Correct 1741 ms 4396 KB Output is correct
17 Correct 2175 ms 5736 KB Output is correct
18 Correct 2209 ms 5652 KB Output is correct
19 Correct 1303 ms 4436 KB Output is correct
20 Correct 2005 ms 5720 KB Output is correct
21 Correct 2009 ms 5720 KB Output is correct
22 Correct 1386 ms 4436 KB Output is correct
23 Correct 4485 ms 11080 KB Output is correct
24 Correct 4809 ms 11124 KB Output is correct
25 Correct 3678 ms 10636 KB Output is correct
26 Correct 6091 ms 9132 KB Output is correct
27 Correct 6780 ms 13872 KB Output is correct
28 Correct 1352 ms 5368 KB Output is correct
29 Correct 1293 ms 5624 KB Output is correct
30 Correct 1349 ms 5496 KB Output is correct
31 Correct 1293 ms 5496 KB Output is correct
32 Correct 5721 ms 13524 KB Output is correct
33 Correct 5487 ms 12984 KB Output is correct
34 Correct 6230 ms 13664 KB Output is correct
35 Correct 5547 ms 13948 KB Output is correct
36 Correct 2455 ms 15164 KB Output is correct
37 Correct 8542 ms 17540 KB Output is correct
38 Correct 6366 ms 12716 KB Output is correct
39 Correct 6134 ms 13740 KB Output is correct
40 Correct 6714 ms 12692 KB Output is correct
41 Correct 8856 ms 15720 KB Output is correct
42 Correct 8939 ms 16072 KB Output is correct