Submission #1292165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292165		ChuanChen	Dancing Elephants (IOI11_elephants)	C++20	Compilation error	0 ms	0 KiB

elephants

#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();
}

Compilation message (stderr)

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;];
      |                                                                 ^