oj.uz

Submission #654090

# Submission time Handle Problem Language Result Execution time Memory
654090 2022-10-29T22:45:06 Z noedit Dancing Elephants (IOI11_elephants) C++17
50 / 100
 806 ms 2656 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 = 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: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:36: 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 = bid[i]; 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 1 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 1 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 1 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 314 ms 1288 KB Output is correct
8 Correct 336 ms 1436 KB Output is correct
9 Correct 468 ms 2424 KB Output is correct
10 Correct 681 ms 2484 KB Output is correct
11 Correct 737 ms 2456 KB Output is correct
12 Correct 806 ms 2396 KB Output is correct
13 Correct 688 ms 2656 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 314 ms 1288 KB Output is correct
8 Correct 336 ms 1436 KB Output is correct
9 Correct 468 ms 2424 KB Output is correct
10 Correct 681 ms 2484 KB Output is correct
11 Correct 737 ms 2456 KB Output is correct
12 Correct 806 ms 2396 KB Output is correct
13 Correct 688 ms 2656 KB Output is correct
14 Incorrect 153 ms 1620 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 314 ms 1288 KB Output is correct
8 Correct 336 ms 1436 KB Output is correct
9 Correct 468 ms 2424 KB Output is correct
10 Correct 681 ms 2484 KB Output is correct
11 Correct 737 ms 2456 KB Output is correct
12 Correct 806 ms 2396 KB Output is correct
13 Correct 688 ms 2656 KB Output is correct
14 Incorrect 153 ms 1620 KB Output isn't correct
15 Halted 0 ms 0 KB -