#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];
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);
for (int i = 0; i < n; i++)
{
bs[i / B].push_back(i);
bid[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];
}
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]);
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:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < bs.size(); i++)
| ~~^~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int j = 0; j < bs[bid[i]].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:125:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int j = bid[i]; j < bs.size(); j++)
| ~~^~~~~~~~~~~
elephants.cpp:138:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int j = 0; j < bs[bid[i]].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
