#include "elephants.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, ii> iii;
typedef pair<ii, ii> iiii;
const int N = 1e6 + 5;
const int oo = 1e9 + 7, mod = 1e9 + 7;
mt19937 rng(1);
ll rnd(ll l, ll r){
ll temp = rng() % (r - l + 1);
return abs(temp) + l;
}
set<ii> mls;
int n, l, arr[N];
pair<int, int> nxt[N][21];
double total = 0;
void rebuild(){
clock_t c1 = clock(), c2;
arr[n] = oo;
vector<ii> v;
for(int i = 0; i <= n; i++) v.pb({arr[i], i});
sort(v.begin(), v.end());
int itr = 0;
for(int i = 0; i <= n; i++){
//cout << arr[i] + l + 1 << "\n";
while(itr < v.size() && (v[itr].fi <= (v[i].fi + l))) itr++;
//vector<ii>::iterator it = lower_bound(v.begin(), v.end(), make_pair(arr[i] + l + 1, -oo));
//nxt[i][0] = (it == v.end() ? make_pair(oo, n) : (*it));
nxt[v[i].se][0] = (itr == v.size() ? make_pair(oo, n) : v[itr]);
//cout << nxt[i][0].fi << " " << nxt[i][0].se << "\n";
}
for(int i = 1; i <= 15; i++){
for(int j = 0; j <= n; j++){
nxt[j][i] = nxt[nxt[j][i - 1].se][i - 1];
//cout << i << " " << j << " " << nxt[j][i].fi << " " << nxt[j][i].se << "\n";
}
}
c2 = clock();
total += ((c2 - c1) / (double)CLOCKS_PER_SEC);
}
int counter = 0;
set<int> poss;
unordered_set<int> ins;
gp_hash_table<int, int> mp1, mp2;
bool all(int pos){
return (mp1[pos] == mp2[pos]);
}
void init(int N, int L, int X[]){
n = N, l = L;
for(ll i = 0; i < n; i++) arr[i] = X[i];
for(ll i = 0; i < n; i++) mls.insert({arr[i], i});
for(int i = 0; i < n; i++) mp1[arr[i]]++;
rebuild();
poss.insert(-1), poss.insert(1e9 + 1);
}
int cnt = 0;
int update(int i, int y){
counter++;
mls.erase({arr[i], i});
mp1[arr[i]]--;
if(ins.find(i) != ins.end()) mp2[arr[i]]--;
poss.insert(arr[i]);
arr[i] = y;
ins.insert(arr[i]);
mp2[arr[i]]++;
poss.insert(arr[i]);
mp1[arr[i]]++;
mls.insert({arr[i], i});
/*
int ans = 0, lst = -1;
for(auto it : mls){
if(lst > it) continue;
ans++;
lst = it + l;
}*/
int ans = 0;
int lst = -1;
bool ck = 1;
for(auto it : poss){
// cout << counter << " " << it << " " << lst << " " << arr[lst] << " " << ans << " " << all(arr[lst]) << "\n";
//cout << ans << " " << lst << "\n";
if(lst < 0){
set<ii>::iterator it2 = mls.lower_bound({it, -oo});
if((it2 != mls.end() && (*it2).fi == it) && (it > (-oo + l))){
ans++;
it2 = mls.lower_bound({-oo + l + 1, -oo});
if(it2 == mls.end()) break;
lst = (*it2).se;
//lst = it;
}
else{
it2 = mls.lower_bound({-oo + l + 1, -oo});
if(it2 == mls.end()) break;
ans++;
lst = (*it2).se;
}
}
else if(all(arr[lst])){
set<ii>::iterator it2 = mls.lower_bound({arr[lst] + l + 1, -oo});
if(it2 == mls.end()) break;
ans++;
lst = (*it2).se;
}
else{
for(int i = 15; i >= 0; i--){
int times = 0;
// cout << i << " " << nxt[lst][i].fi << " " << nxt[lst][i].se << " " << it << "\n";
while(1){
if(nxt[lst][i].fi >= it) break;
times++;
assert(times < 2);
//if(!ck) continue;
ans += (1LL << i);
// assert(arr[nxt[lst][i].se] == nxt[lst][i].fi);
lst = nxt[lst][i].se;
}
}
//cout << ans << " " << lst << " " << arr[lst] << " " << it << "\n";
//set<ii>::iterator it2 = mls.lower_bound({it, -oo});
//cout << arr[lst] + l << " " << ans << "\n";
set<ii>::iterator it2;
if(mp2[it] && (it > (arr[lst] + l))){
ans++;
it2 = mls.lower_bound({it + l + 1, -oo});
// cout << it + l + 1 << " " << (it2 == mls.end()) << "\n";
if(it2 == mls.end()) break;
ans++;
//cout << "OK " << it << " " << it + l + 1 << " " << (*it2).se << "\n";
lst = (*it2).se;
//lst = it;
}
else{
// cout << "OKAY\n";
it2 = mls.lower_bound({arr[lst] + l + 1, -oo});
// cout << arr[lst] + l + 1 << " " << (it2 == mls.end()) << "\n";
// cout << (it2 == mls.end()) << "\n";
if(it2 == mls.end()) break;
ans++;
// cout << "OK " << arr[lst] + l + 1 << " " << (*it2).se << "\n";
lst = (*it2).se;
}
// cout << ans << "\n";
//cout << lst << "\n";
}
ck = 1;
}
cnt++;
// if(!(cnt % 1000)) cout << cnt << " " << "OK " << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
if(!(counter % 50)){
poss.clear();
mp2.clear();
ins.clear();
rebuild();
poss.insert(-1), poss.insert(1e9 + 1);
// cout << cnt << " " << total << " " << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}
return ans;
}
/*
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin >> t;
while(t--) process();
}
*/
Compilation message
elephants.cpp: In function 'void rebuild()':
elephants.cpp:45: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]
45 | while(itr < v.size() && (v[itr].fi <= (v[i].fi + l))) itr++;
| ~~~~^~~~~~~~~~
elephants.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | nxt[v[i].se][0] = (itr == v.size() ? make_pair(oo, n) : v[itr]);
| ~~~~^~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:103:7: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
103 | bool ck = 1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 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 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 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 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 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 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 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 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
