oj.uz

Submission #609566

# Submission time Handle Problem Language Result Execution time Memory
609566 2022-07-27T17:22:56 Z APROHACK Dancing Elephants (IOI11_elephants) C++14
26 / 100
 31 ms 35784 KB 
#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[400000];
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++){
      |                         ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 18 ms 34776 KB Output is correct
3 Correct 21 ms 34716 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 18 ms 34776 KB Output is correct
3 Correct 21 ms 34716 KB Output is correct
4 Correct 17 ms 34772 KB Output is correct
5 Correct 18 ms 34676 KB Output is correct
6 Correct 18 ms 34728 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 18 ms 34776 KB Output is correct
3 Correct 21 ms 34716 KB Output is correct
4 Correct 17 ms 34772 KB Output is correct
5 Correct 18 ms 34676 KB Output is correct
6 Correct 18 ms 34728 KB Output is correct
7 Incorrect 31 ms 35784 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 18 ms 34776 KB Output is correct
3 Correct 21 ms 34716 KB Output is correct
4 Correct 17 ms 34772 KB Output is correct
5 Correct 18 ms 34676 KB Output is correct
6 Correct 18 ms 34728 KB Output is correct
7 Incorrect 31 ms 35784 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 18 ms 34776 KB Output is correct
3 Correct 21 ms 34716 KB Output is correct
4 Correct 17 ms 34772 KB Output is correct
5 Correct 18 ms 34676 KB Output is correct
6 Correct 18 ms 34728 KB Output is correct
7 Incorrect 31 ms 35784 KB Output isn't correct
8 Halted 0 ms 0 KB -