oj.uz

Submission #654092

# Submission time Handle Problem Language Result Execution time Memory
654092 2022-10-29T23:02:29 Z noedit Dancing Elephants (IOI11_elephants) C++17
100 / 100
 6071 ms 11844 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
const int MAXN = 1e5 + 5e4;
const int B = 350;

int n, l, q = 0;

int x[MAXN + 1];

int bid[MAXN + 1];

int go[MAXN + 1];

int cnt[MAXN + 1];

int ord[MAXN + 1];

vector<vector<int> > bs;



void build_block(int num)
{
    int pt = bs[num].size() - 1;
    for (int i = bs[num].size() - 1; i >= 0; i--)
    {
        if (x[bs[num][i]] + l >= x[bs[num].back()])
        {
            go[bs[num][i]] = x[bs[num][i]] + l;
            cnt[bs[num][i]] = 1;
        }
        else
        {
            while (x[bs[num][i]] + l < x[bs[num][pt]])
                pt--;
            go[bs[num][i]] = go[bs[num][pt + 1]];
            cnt[bs[num][i]] = cnt[bs[num][pt + 1]] + 1;
        }
    }
}

void build()
{
    bs.clear();
    fill(go, go + n + 1, -1);
    fill(cnt, cnt + n + 1, 1);
    bs.resize(n / B + 1);
    sort(ord, ord + n, [&](int a, int b){return x[a] < x[b];});
    for (int i = 0; i < n; i++)
    {
        bs[i / B].push_back(ord[i]);
        bid[ord[i]] = i / B;
    }
    for (int i = 0; i < n / B + 1; i++)
    {
        build_block(i);
    }
}

int calc()
{
    int cur = -1;
    int ans = 0;
    for (int i = 0; i < bs.size(); i++)
    {
        if (bs[i].empty())
            continue;
        auto it = upper_bound(bs[i].begin(), bs[i].end(), cur, [&](int val, int elem) {return val < x[elem];});
        if (it == bs[i].end())
        {
            continue;
        }
        ans += cnt[*it];
        cur = go[*it];
    }
    return ans;
}

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    for (int i = 0; i < n; i++)
    {
        x[i] = X[i];
        ord[i] = i;
    }
    build();
}

int update(int i, int y)
{
    q++;
    if (q == 2 * B)
    {
        x[i] = y;
        build();
        q = 0;
    }
    else
    {
        int pt = 0;
        for (int j = 0; j < bs[bid[i]].size(); j++)
        {
            if (bs[bid[i]][j] == i)
            {
                pt = j;
                break;
            }
        }
        bs[bid[i]].erase(bs[bid[i]].begin() + pt);
        build_block(bid[i]);
        pt = 0;
//        if (y <= x[i])
//        {
//            for (int j = 0; j <= bid[i]; j++)
//            {
//                if (bs[j].empty())
//                    continue;
//                if (x[bs[j][0]] <= y)
//                {
//                    pt = j;
//                }
//            }
//        }
//        else
//        {
            for (int j = 0; j < bs.size(); j++)
            {
                if (bs[j].empty())
                    continue;
                if (x[bs[j][0]] <= y)
                {
                    pt = j;
                }
            }
        //}
        x[i] = y;
        bid[i] = pt;
        pt = bs[bid[i]].size();
        for (int j = 0; j < bs[bid[i]].size(); j++)
        {
            if (x[bs[bid[i]][j]] >= x[i])
            {
                pt = j;
                break;
            }
        }
        bs[bid[i]].insert(bs[bid[i]].begin() + pt, i);
        build_block(bid[i]);
    }
//    for (int i = 0; i < bs.size(); i++)
//    {
//        cout << i << " block: \n";
//        for (auto& j : bs[i])
//            cout << j << " " << x[j] << endl;
//    }
    return calc();
}

Compilation message

elephants.cpp: In function 'int calc()':
elephants.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < bs.size(); i++)
      |                     ~~^~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int j = 0; j < bs[bid[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:132:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int j = 0; j < bs.size(); j++)
      |                             ~~^~~~~~~~~~~
elephants.cpp:145:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for (int j = 0; j < bs[bid[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 327 ms 1292 KB Output is correct
8 Correct 346 ms 1432 KB Output is correct
9 Correct 500 ms 2552 KB Output is correct
10 Correct 721 ms 2560 KB Output is correct
11 Correct 776 ms 2512 KB Output is correct
12 Correct 845 ms 2644 KB Output is correct
13 Correct 719 ms 2652 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 327 ms 1292 KB Output is correct
8 Correct 346 ms 1432 KB Output is correct
9 Correct 500 ms 2552 KB Output is correct
10 Correct 721 ms 2560 KB Output is correct
11 Correct 776 ms 2512 KB Output is correct
12 Correct 845 ms 2644 KB Output is correct
13 Correct 719 ms 2652 KB Output is correct
14 Correct 549 ms 1804 KB Output is correct
15 Correct 542 ms 3264 KB Output is correct
16 Correct 1215 ms 4680 KB Output is correct
17 Correct 1464 ms 5336 KB Output is correct
18 Correct 1586 ms 5416 KB Output is correct
19 Correct 1322 ms 5532 KB Output is correct
20 Correct 1467 ms 5368 KB Output is correct
21 Correct 1488 ms 5300 KB Output is correct
22 Correct 1339 ms 4936 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 327 ms 1292 KB Output is correct
8 Correct 346 ms 1432 KB Output is correct
9 Correct 500 ms 2552 KB Output is correct
10 Correct 721 ms 2560 KB Output is correct
11 Correct 776 ms 2512 KB Output is correct
12 Correct 845 ms 2644 KB Output is correct
13 Correct 719 ms 2652 KB Output is correct
14 Correct 549 ms 1804 KB Output is correct
15 Correct 542 ms 3264 KB Output is correct
16 Correct 1215 ms 4680 KB Output is correct
17 Correct 1464 ms 5336 KB Output is correct
18 Correct 1586 ms 5416 KB Output is correct
19 Correct 1322 ms 5532 KB Output is correct
20 Correct 1467 ms 5368 KB Output is correct
21 Correct 1488 ms 5300 KB Output is correct
22 Correct 1339 ms 4936 KB Output is correct
23 Correct 3717 ms 11844 KB Output is correct
24 Correct 3930 ms 11784 KB Output is correct
25 Correct 3255 ms 11652 KB Output is correct
26 Correct 5863 ms 11656 KB Output is correct
27 Correct 5647 ms 11648 KB Output is correct
28 Correct 1309 ms 5172 KB Output is correct
29 Correct 1268 ms 5172 KB Output is correct
30 Correct 1350 ms 5176 KB Output is correct
31 Correct 1298 ms 5168 KB Output is correct
32 Correct 6071 ms 11184 KB Output is correct
33 Correct 4091 ms 10444 KB Output is correct
34 Correct 5259 ms 11444 KB Output is correct
35 Correct 3972 ms 11684 KB Output is correct
36 Correct 3211 ms 11260 KB Output is correct
37 Correct 5345 ms 11628 KB Output is correct
38 Correct 5222 ms 10436 KB Output is correct
39 Correct 4994 ms 11640 KB Output is correct
40 Correct 5284 ms 10428 KB Output is correct
41 Correct 5886 ms 11072 KB Output is correct
42 Correct 5680 ms 11452 KB Output is correct