oj.uz

Submission #654091

# Submission time Handle Problem Language Result Execution time Memory
654091 2022-10-29T22:52:55 Z noedit Dancing Elephants (IOI11_elephants) C++17
50 / 100
 808 ms 2556 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 = 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 = 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 1 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 1 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 0 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 1 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 0 ms 340 KB Output is correct
7 Correct 330 ms 1292 KB Output is correct
8 Correct 336 ms 1432 KB Output is correct
9 Correct 478 ms 2392 KB Output is correct
10 Correct 695 ms 2556 KB Output is correct
11 Correct 744 ms 2492 KB Output is correct
12 Correct 808 ms 2512 KB Output is correct
13 Correct 700 ms 2400 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 1 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 0 ms 340 KB Output is correct
7 Correct 330 ms 1292 KB Output is correct
8 Correct 336 ms 1432 KB Output is correct
9 Correct 478 ms 2392 KB Output is correct
10 Correct 695 ms 2556 KB Output is correct
11 Correct 744 ms 2492 KB Output is correct
12 Correct 808 ms 2512 KB Output is correct
13 Correct 700 ms 2400 KB Output is correct
14 Incorrect 145 ms 1688 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 1 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 0 ms 340 KB Output is correct
7 Correct 330 ms 1292 KB Output is correct
8 Correct 336 ms 1432 KB Output is correct
9 Correct 478 ms 2392 KB Output is correct
10 Correct 695 ms 2556 KB Output is correct
11 Correct 744 ms 2492 KB Output is correct
12 Correct 808 ms 2512 KB Output is correct
13 Correct 700 ms 2400 KB Output is correct
14 Incorrect 145 ms 1688 KB Output isn't correct
15 Halted 0 ms 0 KB -