#include "elephants.h" #include<bits/stdc++.h> using namespace std; const int B_QTD = 120, B_SZ = 1255, 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){ for(int l = v.size()-1, r = v.size(); l >= 0; l--){ while( posicao[ v[l] ] + L < pos[ v[r-1] ]) r--; //garanto que r eh primeuiro que n consigo cobrir if(r == v.size()){//caso eu cobro tudo mundo photo[ v[l] ] = 1; ult_coberto[ v[l] ] = posicao[ v[l] ]+L; } else{ photo[ v[l] ] = 1+photo[ v[r] ]; ult_coberto[ v[l] ] = ult_coberto[ v[r] ]; } } } //cada assign bucket deve ser feito em O(n) void assign_buckets(){ for(int i = 0; i < B_QTD; i++) buckets[i].clear(); for(auto it = eleph_in_order.begin(), id = 1; it != eleph_in_order.end(); ++it, ++id){ myb[id] = get_bucket(id); buckets[myb[id]].push_back(i); } 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_SZ){ //bucket i, j-ésimo elefante vai começar foto int no = buckets[i][j]; ans += photo[no]; int uc = ult_coberto[no]; while( i+1 < B_SZ && pos[ buckets[i+1][0] ] <= uc ) i++; //i := ultimo buckets que tem elephante incluido no foto j = 0; for(int k = 11; k >= 0; k--){//cada buckets tem maximo 1250 elefantes if(j + (1<<k) >= buckets[i].size()) continue; if( pos[ buckets[i][j+(1<<k)] ] <= uc ) j += (1<<k); } j++; if(j == buckets[i].size()){ j = 0; i++; } } 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(); } //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] ]; antigo.erase(lower_bound(antigo.begin(), antigo.end(), i)); make_bucket(antigo); //recalcula bucket que me ganhou myb[i] = myb[eleph_in_order.upper_bound({y, i})->second;]; vector<int> &novo = buckets[ myb[i] ]; novo.insert(--lower_bound(novo.begin(), novo.end(), i), i); make_bucket(novo); } return find_answer(); }

elephants.cpp: In function 'void make_bucket(std::vector<int>&)':
elephants.cpp:20:38: error: 'pos' was not declared in this scope; did you mean 'pow'?
   20 |         while( posicao[ v[l] ] + L < pos[ v[r-1] ]) r--;
      |                                      ^~~
      |                                      pow
elephants.cpp: In function 'void assign_buckets()':
elephants.cpp:37:9: error: inconsistent deduction for 'auto': 'std::_Rb_tree_const_iterator<std::pair<int, int> >' and then 'int'
   37 |     for(auto it = eleph_in_order.begin(), id = 1; it != eleph_in_order.end(); ++it, ++id){
      |         ^~~~
elephants.cpp:39:36: error: 'i' was not declared in this scope; did you mean 'id'?
   39 |         buckets[myb[id]].push_back(i);
      |                                    ^
      |                                    id
elephants.cpp: In function 'int find_answer()':
elephants.cpp:53:30: error: 'pos' was not declared in this scope; did you mean 'pow'?
   53 |         while( i+1 < B_SZ && pos[ buckets[i+1][0] ] <= uc ) i++;
      |                              ^~~
      |                              pow
elephants.cpp:58:17: error: 'pos' was not declared in this scope; did you mean 'pow'?
   58 |             if( pos[ buckets[i][j+(1<<k)] ] <= uc ) j += (1<<k);
      |                 ^~~
      |                 pow
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:74:26: error: expected ';' before 'eleph_in_order'
   74 |         posicao[i] = X[i]
      |                          ^
      |                          ;
   75 |         eleph_in_order.insert({X[i], i});
      |         ~~~~~~~~~~~~~~    
elephants.cpp:75:40: error: expected primary-expression before ')' token
   75 |         eleph_in_order.insert({X[i], i});
      |                                        ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:100:64: error: expected ']' before ';' token
  100 |         myb[i] = myb[eleph_in_order.upper_bound({y, i})->second;];
      |                                                                ^
      |                                                                ]
elephants.cpp:100:65: error: expected primary-expression before ']' token
  100 |         myb[i] = myb[eleph_in_order.upper_bound({y, i})->second;];
      |                                                                 ^