#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
int n, l;
const int N = 150010;
const int B = 4;
map <pair <int, int>, int> res, pai, bloco;
set <pair <int, int>> s;
int val[N];
void init(int NN, int L, int x[]){
n = NN;
l = L;
res[{x[n-1], n-1}] = 1;
pai[{x[n-1], n-1}] = 1e9+10;
for(int i = 0;i < n;i++){
int d = i/B;
bloco[{x[i], i}] = d*B;
val[i] = x[i];
}
s.insert({x[n-1], n-1});
for(int i = n-2;i >= 0;i--){
auto it = s.upper_bound({x[i]+l, 1e9});
if(it == s.end()){
res[{x[i], i}] = 1;
pai[{x[i], i}] = 1e9+10;
}
else{
pair <int, int> d = *it;
res[{x[i], i}] = (bloco[d] != bloco[{x[i], i}] ? 1 : res[d]+1);
pai[{x[i], i}] = (bloco[d] != bloco[{x[i], i}] ? d.first : pai[d]);
}
s.insert({x[i], i});
}
return;
}
int cnt = 0;
void remover(int i, int y){
cnt++;
int t = val[i];
//cout << i << ' ' << y << '\n';
auto it = s.find({val[i], i});
int cu = bloco[{t, i}];
s.erase(it);
it = s.lower_bound({val[i], i});
while(bloco[{t, i}] == bloco[*it]){
if(it == s.end()) break;
it++;
if(it == s.end()) break;
}
res.erase({val[i], i});
pai.erase({val[i], i});
bloco.erase({val[i], i});
val[i] = y;
if(it == s.begin()) return;
it--;
pair <int, int> valor = *it;
it = s.find(valor);
while(bloco[valor] == cu){
//cout << valor.first << ' ' << valor.second << '\n';
auto itt = s.upper_bound({valor.first+l, 1e9});
if(itt == s.end()){
res[valor] = 1;
pai[valor] = 1e9+10;
if(it == s.begin()) break;
it--;
valor = *it;
//cout << valor.first << ' ' << valor.second << '\n';
continue;
}
pair <int, int> d = *itt;
if(bloco[d] != bloco[valor]){
res[valor] = 1;
pai[valor] = d.first;
}
else{
res[valor] = res[d]+1;
pai[valor] = pai[d];
}
if(it == s.begin()) break;
it--;
valor = *it;
}
cu = bloco[valor];
while(bloco[valor] == cu){
auto itt = s.upper_bound({valor.first+l, 1e9});
if(itt == s.end()){
res[valor] = 1;
pai[valor] = 1e9+10;
if(it == s.begin()) break;
it--;
valor = *it;
continue;
}
pair <int, int> d = *itt;
if(bloco[d] != bloco[valor]){
res[valor] = 1;
pai[valor] = d.first;
}
else{
res[valor] = res[d]+1;
pai[valor] = pai[d];
}
if(it == s.begin()) break;
it--;
valor = *it;
}
}
void addd(int i, int y){
val[i] = y;
auto it = s.lower_bound({y, 0});
if(it == s.begin()){
bloco[{y, i}] = bloco[*it];
}
else{
auto it2 = prev(it);
bloco[{y, i}] = bloco[*it2];
}
int bl = bloco[{y, i}];
s.insert({y, i});
it = s.find({y, i});
while(bloco[*it] == bl){
it++;
if(it == s.end()) break;
}
int tam = 0;
it--;
while(bloco[*it] == bl){
tam++;
if(it == s.begin()) break;
it--;
}
if(tam > 2*B){
tam = 0;
while(bloco[*it] == bl and tam < B){
tam++;
it++;
}
while(bloco[*it] == bl){
tam++;
bloco[*it]++;
it++;
}
}
else{
it++;
if(it != s.end()){
while(bloco[*it] == bl){
it++;
if(it == s.end()) break;
}
}
}
it--;
pair <int, int> valor = *it;
int cu = bloco[valor];
it = s.find(valor);
while(bloco[valor] == cu){
auto itt = s.upper_bound({valor.first+l, 1e9});
if(itt == s.end()){
res[valor] = 1;
pai[valor] = 1e9+10;
if(it == s.begin()) break;
it--;
valor = *it;
continue;
}
pair <int, int> d = *itt;
if(bloco[d] != bloco[valor]){
res[valor] = 1;
pai[valor] = d.first;
}
else{
res[valor] = res[d]+1;
pai[valor] = pai[d];
}
if(it == s.begin()) break;
it--;
valor = *it;
}
cu = bloco[valor];
while(bloco[valor] == cu){
auto itt = s.upper_bound({valor.first+l, 1e9});
if(itt == s.end()){
res[valor] = 1;
pai[valor] = 1e9+10;
if(it == s.begin()) break;
it--;
valor = *it;
continue;
}
pair <int, int> d = *itt;
if(bloco[d] != bloco[valor]){
res[valor] = 1;
pai[valor] = d.first;
}
else{
res[valor] = res[d]+1;
pai[valor] = pai[d];
}
if(it == s.begin()) break;
it--;
valor = *it;
}
while(bloco[valor] == cu){
auto itt = s.upper_bound({valor.first+l, 1e9});
pair <int, int> d = *itt;
if(itt == s.end()){
res[valor] = 1;
pai[valor] = 1e9+10;
if(it == s.begin()) break;
it--;
valor = *it;
continue;
}
if(bloco[d] != bloco[valor]){
res[valor] = 1;
pai[valor] = d.first;
}
else{
res[valor] = res[d]+1;
pai[valor] = pai[d];
}
if(it == s.begin()) break;
it--;
valor = *it;
}
return;
}
int update(int i, int y){
/*for(auto [p, x] : pai){
auto [val, i] = p;
cout << val << ' ' << i << ' ' << x << ' ' << res[{val, i}] << endl;
}*/
remover(i, y);
/*for(auto [p, x] : pai){
auto [val, i] = p;
cout << val << ' ' << i << ' ' << x << ' ' << res[{val, i}] << ' ' << bloco[{val, i}] << endl;
}*/
addd(i, y);
/*for(auto [p, x] : pai){
auto [val, i] = p;
cout << val << ' ' << i << ' ' << x << ' ' << res[{val, i}] << ' ' << bloco[{val, i}] << endl;
}*/
int ans = 0;
auto it = s.begin();
while(it != s.end()){
pair <int, int> aux = *it;
ans += res[aux];
int nx = pai[aux];
//cout << nx << ' ';
it = s.lower_bound({nx, -1});
//cout << (*it).first << '\n';
}
//if(cnt == 1) exit(0);
//cout << '\n';
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
