#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<int, int > >arr; // valor, indx
pair <int, int> mapeo[150005]; // donde en arr, cual bloque
struct bloque
{
vector<int>values;
vector<int>camarasDesde;
vector<int>terminaenDesde;
int Desde, indiceDelBloque, componentes;//posicion
void setIndice(int indice){
indiceDelBloque = indice;
if(indice == 0)Desde = 0;
}
void llenarConArreglo(){
int end = min(n, (indiceDelBloque+1)*blocksz);
values.clear(), camarasDesde.clear(), terminaenDesde.clear();
for(int 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(){
int 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--;
}
printall();
}
void reconstruir(){
llenarConArreglo();
actualizar();
}
void printall(){
//cout << "bloque "<<indiceDelBloque << endl;
////cout << values.size() << componentes << endl;
for(int i = 0 ; i < componentes ; i++){
//cout << values[i] << " ";
}
//cout << endl;
for(int i = 0 ; i < componentes ; i++){
//cout << camarasDesde[i] << " ";
}
//cout << endl;
for(int i = 0 ; i < componentes ; i++){
//cout << terminaenDesde[i] << " ";
}
//cout << endl;
}
void quitar(int value){
for (int i = 0; i < values.size(); i++){
if(values[i] == value){
values[i] = -1;
break;
}
}
vector<int>temp;
for(int 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<int, int> answer(int last){ // camaras, last
if(values.empty())return {0, last};
int position = (upper_bound(values.begin(), values.end(), last)-values.begin());
if(values[position]<=last)return {0, last};
return {camarasDesde[position], terminaenDesde[position]};
}
void agregar(int value){
vector<int>temp;
int where = -1;
for(int 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(int 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];
int q;
void init(int N, int L, int X[])
{
n = N, l = L;
blocksz = sqrt(n);
q = blocksz ;
//////cout<<blocksz<<endl;
for(int i = 0 ; i < n ; i++){
arr.pb({X[i], i});
}
for(int i = 0 ; i < blocksz +1 ; i ++){
bloques [ i ].setIndice(i);
}
}
void reconstruirTodo(){
sort(arr.begin(), arr.end());
int id = 0;
for(auto i : arr){
mapeo[i.ss].ff = id++;
}
for(int i = 0 ; i < blocksz+1 ; i++){
bloques[i].reconstruir();
}
}
int encontrarBloque(int y){
int last = -1, ans=blocksz;
for(int i = 0 ; i < blocksz +1 ; i++){
last = bloques[i].answer(last).ss;
if(last>y){
ans = i;
return ans;
}
}
return ans;
}
int current = 1;
int hallarRta(){
//cout<<"c"<<current++<<endl;
int last = -1, ans = 0;
for(int i = 0 ; i < blocksz +1 ; i++){
pair<int, int>rta = bloques[i].answer(last);
ans+=rta.ff;
//cout<<"ans of "<< i << " = "<< rta.ff << " finish " << rta.ss<<endl;
last = rta.ss;
}
return ans;
}
int update(int i, int y)
{
if(q==blocksz){
reconstruirTodo();
q=-1;
}
//cout<<"added"<<arr[mapeo[i].ff].ff << " -> " <<y << "er" << mapeo[i].ss<< endl;
q++;
bloques[mapeo[i].ss].quitar(arr[mapeo[i].ff].ff);
arr[mapeo[i].ff].ff = y;
mapeo[i].ss=encontrarBloque(y);
bloques[mapeo[i].ss].agregar(y);
return hallarRta();
}
Compilation message
elephants.cpp: In member function 'void bloque::quitar(int)':
elephants.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < values.size(); i++){
| ~~^~~~~~~~~~~~~~~
elephants.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0 ; i < values.size() ; i++){
| ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void bloque::agregar(int)':
elephants.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 0 ; i < values.size() ; i++){
| ~~^~~~~~~~~~~~~~~
elephants.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0 ; i < temp.size() ; i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
2320 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
2320 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
2320 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
