#include "elephants.h" #include<bits/stdc++.h> using namespace std; #define db(v) //cerr << #v << ": " << v << " "; #define dbln(v) //cerr << #v << ": " << v << endl; const int B_QTD = 120, B_SZ = 1255, Q = 400, MAXN = 150010; // const int B_QTD = 150000, B_SZ = 1, Q = 400, MAXN = 150010; // const int B_QTD = 1, B_SZ = 150000, Q = 400, MAXN = 150010; int n, L, q_cnt; int photo[MAXN], ult_coberto[MAXN], posicao[MAXN], myb[MAXN]; //photo[i] := comecando elephante i, #photo para terminar esse bucket //ult_coberto[i]:= ultimo coordenada que meus photos cobri //myb[i] := bucket que i pertence atualmente set<pair<int, int>> eleph_in_order; //{posicao, id} vector<int> buckets[B_QTD]; //id dos elephante ordenandas dividas nos buckets int get_bucket(int i){ return i/B_SZ; } void make_bucket(vector<int> &v){ if(v.empty()) return; //cerr << "nesse bucket contem: "; //for(int id : v) //cerr << id << ' '; //cerr << endl; for(int l = v.size()-1, r = v.size(); l >= 0; l--){ while( posicao[ v[l] ] + L < posicao[ v[r-1] ]) r--; //garanto que r eh primeuiro que n consigo cobrir if(r == (int)v.size()){//caso eu cobro tudo mundo dbln("*") photo[ v[l] ] = 1; ult_coberto[ v[l] ] = posicao[ v[l] ]+L; db(v[l]) db(photo[v[l]]) db(posicao[v[l]]) dbln(ult_coberto[v[l]]); } else{ photo[ v[l] ] = 1+photo[ v[r] ]; ult_coberto[ v[l] ] = ult_coberto[ v[r] ]; db(v[l]) db(photo[v[l]]) dbln(ult_coberto[v[l]]); } } } //cada assign bucket deve ser feito em O(n) void assign_buckets(){ for(int i = 0; i < B_QTD; i++) buckets[i].clear(); int i = 0; for(auto it = eleph_in_order.begin(); it != eleph_in_order.end(); ++it, ++i){ int id = it->second; myb[id] = get_bucket(i); //cerr << "bucket " << myb[id] << " contem " << id << "\n"; buckets[myb[id]].push_back(id); } for(int i = B_QTD; i >= 0; i--) make_bucket(buckets[i]); } int find_answer(){ int ans = 0; int i = 0, j = 0; while(i < B_QTD){ //bucket i, j-ésimo elefante vai começar foto if(buckets[i].empty()){ i++; continue; } int no = buckets[i][j]; dbln(no); ans += photo[no]; int uc = ult_coberto[no]; int li = 0; for(; i < B_QTD; i++){ if(buckets[i].empty()) continue; dbln(i); //cerr << "nesse bucket contem: "; //for(int id : buckets[i]) //cerr << id << ' '; //cerr << endl; if(posicao[ buckets[i][0] ] <= uc) li = i; if(posicao[ buckets[i].back() ] > uc) break; } //i := ultimo buckets que tem elephante incluido no foto j = 0; dbln(li); for(int k = 11; k >= 0; k--){//cada buckets tem maximo 1250 elefantes if(j + (1<<k) >= (int)buckets[li].size()) continue; if( posicao[ buckets[li][j+(1<<k)] ] <= uc ) j += (1<<k); dbln(j); } j++; //j:= quem eu n consigo pegar if(j >= (int)buckets[li].size()){ j = 0; i = li+1; } dbln(i); dbln(j); } dbln(ans); return ans; } void init(int N, int _L, int X[]){ n = N; L = _L; for(int i = 0; i < n; i++){ posicao[i] = X[i]; eleph_in_order.insert({X[i], i}); } assign_buckets(); // int ans0 = find_answer(); // dbln(ans0); } //muda elephante i para posicao y int update(int i, int y){ q_cnt++; int pos0 = posicao[i]; posicao[i] = y; eleph_in_order.erase({pos0, i}); eleph_in_order.insert({y, i}); if(q_cnt == Q){ assign_buckets(); q_cnt = 0; } else{ //recalcula bucket que me perdeu vector<int> &antigo = buckets[ myb[i] ]; int id = 0; while(id < (int)antigo.size() && antigo[id] != i) id++; ////cerr << "deletar " << antigo[id] << " do bucket " << myb[i] << endl; antigo.erase(antigo.begin()+id); //cerr << "bucket " << myb[i] << " tem tamanho " << buckets[myb[i]].size() << endl; db(i) dbln(y); dbln(myb[i]); dbln("antigo") //for(int a : antigo) //cerr << a << ' '; //cerr << endl; make_bucket(antigo); //recalcula bucket que me ganhou auto frente_de_mim = eleph_in_order.upper_bound({y, i}); if(frente_de_mim == eleph_in_order.end()) --frente_de_mim, --frente_de_mim; dbln(frente_de_mim->second); myb[i] = myb[frente_de_mim->second]; vector<int> &novo = buckets[ myb[i] ]; id = 0; while(id < (int)novo.size() && posicao[ novo[id] ] < y) id++; //cerr << "adictionar " << i << " no bucket " << myb[i] << " no pos " << id << endl; novo.insert(novo.begin()+id, i); dbln("novo") //for(int a : novo) //cerr << a << ' '; //cerr << endl; make_bucket(novo); } return find_answer(); }