oj.uz

Submission #654089

# Submission time Handle Problem Language Result Execution time Memory
654089 2022-10-29T22:33:28 Z noedit Dancing Elephants (IOI11_elephants) C++17
50 / 100
 846 ms 3800 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++)
    {
        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 = bid[i];
        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 = bid[i]; 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:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int j = 0; j < bs[bid[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:130:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             for (int j = bid[i]; j < bs.size(); j++)
      |                                  ~~^~~~~~~~~~~
elephants.cpp:143:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         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 0 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 0 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 0 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 328 ms 1300 KB Output is correct
8 Correct 334 ms 1360 KB Output is correct
9 Correct 475 ms 2412 KB Output is correct
10 Correct 710 ms 2544 KB Output is correct
11 Correct 779 ms 3668 KB Output is correct
12 Correct 846 ms 3800 KB Output is correct
13 Correct 735 ms 3644 KB Output is correct

Subtask #4
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 0 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 328 ms 1300 KB Output is correct
8 Correct 334 ms 1360 KB Output is correct
9 Correct 475 ms 2412 KB Output is correct
10 Correct 710 ms 2544 KB Output is correct
11 Correct 779 ms 3668 KB Output is correct
12 Correct 846 ms 3800 KB Output is correct
13 Correct 735 ms 3644 KB Output is correct
14 Incorrect 155 ms 3192 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
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 0 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 328 ms 1300 KB Output is correct
8 Correct 334 ms 1360 KB Output is correct
9 Correct 475 ms 2412 KB Output is correct
10 Correct 710 ms 2544 KB Output is correct
11 Correct 779 ms 3668 KB Output is correct
12 Correct 846 ms 3800 KB Output is correct
13 Correct 735 ms 3644 KB Output is correct
14 Incorrect 155 ms 3192 KB Output isn't correct
15 Halted 0 ms 0 KB -