#include "elephants.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef pair<int, int> pii;
const int MxN=150001, C=388, INF=1e9;
int n, l, x[MxN], dp[MxN], far[MxN], gr[MxN], max_block;
vector<pii> block[C];
void build_block(int in)
{
int j=block[in].size();
for(int k=block[in].size()-1; k>=0; k--){
int i=block[in][k].s;
while(j-1>k && block[in][j-1].f>x[i]+l) j--;
if(j==block[in].size()) dp[i]=1, far[i]=x[i]+l;
else{
int nxt=block[in][j].s;
dp[i]=dp[nxt]+1;
far[i]=far[nxt];
}
}
}
void build()
{
vector<pii> vec;
FOR(i, 0, n) vec.pb({x[i],i});
sort(vec.begin(), vec.end()); // might be possible to optimize this
FOR(i, 0, max_block+1) block[i].clear();
max_block=0;
FOR(i, 0, n)
{
int in=i/C;
block[in].pb(vec[i]);
gr[vec[i].s]=in;
max_block=max(max_block, in);
}
FOR(i, 0, max_block+1) build_block(i);
}
void change_pos(int i, int y)
{
int in=gr[i];
block[in].erase(lower_bound(block[in].begin(), block[in].end(), make_pair(x[i],i)));
build_block(in);
x[i]=y;
int nxt_in=0;
FOR(id, 0, max_block+1) // might be possible to optimize this
{
if(block[id].empty()) continue;
if(block[id][0].f<=x[i]) nxt_in=i;
}
gr[i]=nxt_in;
block[nxt_in].insert(upper_bound(block[nxt_in].begin(), block[nxt_in].end(), make_pair(x[i],i)), {x[i],i});
build_block(nxt_in);
}
int answer()
{
int farr=-1, ret=0;
FOR(i, 0, max_block+1)
{
if(block[i].empty() || block[i].back().f<=farr) continue;
int l0=0, r0=block[i].size();
while(l0<r0){
int m=(l0+r0)/2;
if(block[i][m].f>farr) r0=m;
else l0=m+1;
}
// cout << i << ": " << l0 << '\n';
assert(l0<block[i].size());
assert(block[i][l0].f>farr);
ret+=dp[block[i][l0].s];
farr=far[block[i][l0].s];
}
return ret;
}
void print_block(int in)
{
for(auto it : block[in]){
cout << it.f << " " << it.s << '\n';
}
}
void print_blocks()
{
FOR(i, 0, max_block+1)
{
cout << "block " << i << ":\n";
print_block(i);
}
}
void init(int N, int L, int X[])
{
n=N; l=L; FOR(i, 0, n) x[i]=X[i];
}
int counter=0;
int update(int i, int y)
{
if(counter%C==0) build();
change_pos(i, y);
counter++;
// cout << "update (" << i << ", " << y << "):\n";
//
// print_blocks();
return answer();
}
Compilation message
elephants.cpp: In function 'void build_block(int)':
elephants.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | if(j==block[in].size()) dp[i]=1, far[i]=x[i]+l;
| ~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from elephants.cpp:3:
elephants.cpp: In function 'int answer()':
elephants.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | assert(l0<block[i].size());
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
