#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll n, l, blocksz, st;
vector<pair<ll, ll > >arr; // valor, indx
pair <ll, ll> mapeo[150005]; // donde en arr, cual bloque
struct bloque
{
vector<ll>values;
vector<ll>camarasDesde;
vector<ll>terminaenDesde;
ll Desde, indiceDelBloque, componentes;//posicion
void setIndice(ll indice){
indiceDelBloque = indice;
if(indice == 0)Desde = 0;
}
void llenarConArreglo(){
ll end = min(n, (indiceDelBloque+1)*blocksz);
values.clear(), camarasDesde.clear(), terminaenDesde.clear();
for(ll i = indiceDelBloque * blocksz ; i < end ; ++i){
////cout<<"ll "<<i<<endl;
values.pb(arr[i].ff);
camarasDesde.pb(1);
terminaenDesde.pb(values.back()+l);
mapeo[arr[i].ss]={i, indiceDelBloque};
}
camarasDesde.pb(0);
terminaenDesde.pb(0);
componentes = values.size();
}
void actualizar(){
ll i=componentes-1, j = componentes;
while(i+1!=0){
while(values[i]+l<values[j-1])j--;
////cout << i << " " << j <<endl;
camarasDesde[i]=camarasDesde[j]+1;
terminaenDesde[i] = j!=componentes ? terminaenDesde[j] : values[i]+l;
i--;
}
prllall();
}
void reconstruir(){
llenarConArreglo();
actualizar();
}
void prllall(){
//cout << "bloque "<<indiceDelBloque << endl;
//cout << values.size() << componentes << endl;
for(ll i = 0 ; i < componentes ; i++){
//cout << values[i] << " ";
}
// cout << endl;
for(ll i = 0 ; i < componentes ; i++){
//cout << camarasDesde[i] << " ";
}
//cout << endl;
for(ll i = 0 ; i < componentes ; i++){
//cout << terminaenDesde[i] << " ";
}
//cout << endl;
}
void quitar(ll value){
for (ll i = 0; i < values.size(); i++){
if(values[i] == value){
values[i] = -1;
break;
}
}
vector<ll>temp;
for(ll i = 0 ; i < values.size() ; i++){
if(values[i]!=-1)temp.pb(values[i]);
}
values.clear(), camarasDesde.clear(), terminaenDesde.clear();
for(auto i : temp){
values.pb(i);
camarasDesde.pb(1);
terminaenDesde.pb(values.back()+l);
//mapeo[arr[i].ss]={i, indiceDelBloque};
}
camarasDesde.pb(0);
terminaenDesde.pb(0);
componentes = values.size();
actualizar();
}
pair<ll, ll> answer(ll last){ // camaras, last
if(values.empty())return {0, last};
ll position = (upper_bound(values.begin(), values.end(), last)-values.begin());
if(values[position]<=last)return {0, last};
return {camarasDesde[position], terminaenDesde[position]};
}
void agregar(ll value){
vector<ll>temp;
ll where = -1;
for(ll i = 0 ; i < values.size() ; i++){
if(values[i]<value)where = i;
temp.pb(values[i]);
}
values.clear(), camarasDesde.clear(), terminaenDesde.clear();
if(where==-1){
values.pb(value);
camarasDesde.pb(1);
terminaenDesde.pb(values.back()+l);
}
for(ll i = 0 ; i < temp.size() ; i++){
values.pb(temp[i]);
camarasDesde.pb(1);
terminaenDesde.pb(values.back()+l);
if(i==where){
values.pb(value);
camarasDesde.pb(1);
terminaenDesde.pb(values.back()+l);
}
//mapeo[arr[i].ss]={i, indiceDelBloque};
}
camarasDesde.pb(0);
terminaenDesde.pb(0);
componentes = values.size();
actualizar();
}
};
bloque bloques[1400];
ll q;
void init(ll N, ll L, ll X[])
{
n = N, l = L;
blocksz = sqrt(n);
q = blocksz ;
//cout<<blocksz<<endl;
for(ll i = 0 ; i < n ; i++){
arr.pb({X[i], i});
}
for(ll i = 0 ; i < blocksz +1 ; i ++){
bloques [ i ].setIndice(i);
}
}
void reconstruirTodo(){
sort(arr.begin(), arr.end());
ll id = 0;
for(auto i : arr){
mapeo[i.ss].ff = id++;
}
for(ll i = 0 ; i < blocksz+1 ; i++){
bloques[i].reconstruir();
}
}
ll encontrarBloque(ll y){
ll last = -1, ans=blocksz;
for(ll i = 0 ; i < blocksz +1 ; i++){
last = bloques[i].answer(last).ss;
if(last>y){
ans = i;
return ans;
}
}
return ans;
}
ll hallarRta(){
ll last = -1, ans = 0;
for(ll i = 0 ; i < blocksz +1 ; i++){
pair<ll, ll>rta = bloques[i].answer(last);
ans+=rta.ff;
//cout<<"ans of "<< i << " = "<< rta.ff << " finish " << rta.ss<<endl;
last = rta.ss;
}
return ans;
}
ll update(ll i, ll y)
{
if(q==blocksz){
reconstruirTodo();
q=-1;
}
q++;
bloques[mapeo[i].ss].quitar(arr[mapeo[i].ff].ff);
arr[mapeo[i].ff].ff = y;
bloques[encontrarBloque(y)].agregar(y);
return hallarRta();
}
Compilation message
elephants.cpp: In member function 'void bloque::quitar(long long int)':
elephants.cpp:69:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (ll i = 0; i < values.size(); i++){
| ~~^~~~~~~~~~~~~~~
elephants.cpp:77:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(ll i = 0 ; i < values.size() ; i++){
| ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void bloque::agregar(long long int)':
elephants.cpp:103:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(ll i = 0 ; i < values.size() ; i++){
| ~~^~~~~~~~~~~~~~~
elephants.cpp:113:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(ll i = 0 ; i < temp.size() ; i++){
| ~~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc2akS7W.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x56): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status
