Submission #255396

#	Time	Username	Problem	Language	Result	Execution time	Memory
255396		Sorting	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	8440 ms	19884 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int k_N = 15e4 + 3;
const int k_B = 1500;
 
void calc_p(int i);

int n, l;
int *x;

vector<vector<int>> idx, val;
vector<vector<array<int, 2>>> p;
map<int, int> mp;

void init(int N, int L, int X[]){
    n = N;
    l = L;
    x = X;
    
    for(int i = 0; i < n; ++i){
        if(idx.empty() || idx.back().size() >= k_B){
            idx.push_back({});
            val.push_back({});
        }
        idx.back().push_back(i);
        val.back().push_back(x[i]);
        mp[i] = (int)idx.size() - 1;
    }

    p.clear();
    p.resize(idx.size());
    for(int i = 0; i < idx.size(); ++i)
        calc_p(i);
}

int get_ans(){
    int bigger = -1, ans = 0;
    for(int i = 0; i < idx.size(); ++i){
        auto it = upper_bound(val[i].begin(), val[i].end(), bigger);
        if(it == val[i].end()) continue;

        int j = it - val[i].begin();
        ans += p[i][j][0];
        bigger = p[i][j][1];
    }
    return ans;
}

void calc_p(int i){
    int ptr = idx[i].size();
    p[i].resize(idx[i].size());
    for(int j = (int)idx[i].size() - 1; j >= 0; --j){
        while(val[i][ptr - 1] - val[i][j] > l)
            ptr--;
        if(ptr == idx[i].size())
            p[i][j] = {1, val[i][j] + l};
        else
            p[i][j] = {p[i][ptr][0] + 1, p[i][ptr][1]};
    }
}

void rebuild(){
    vector<int> val_tmp;
    vector<int> idx_tmp;

    for(int i = 0; i < idx.size(); ++i){
        for(int x: idx[i])
            idx_tmp.push_back(x);
        for(int x: val[i])
            val_tmp.push_back(x);
    }

    idx.clear();
    val.clear();

    for(int i = 0; i < val_tmp.size(); ++i){
        if(idx.empty() || idx.back().size() >= k_B){
            idx.push_back({});
            val.push_back({});
        }
        idx.back().push_back(idx_tmp[i]);
        val.back().push_back(val_tmp[i]);
        mp[idx_tmp[i]] = (int)idx.size() - 1;
    }

    p.clear();
    p.resize(idx.size());
    for(int i = 0; i < idx.size(); ++i)
        calc_p(i);
}

void remove(int t, int i){
    int j = mp[i];
    for(int k = 0; k < idx[j].size(); ++k){
        if(idx[j][k] == i){
            idx[j].erase(idx[j].begin() + k);
            val[j].erase(val[j].begin() + k);
            break;
        }
    }
    calc_p(j);
}

void add(int t, int i){
    int j;
    for(j = 0; j < idx.size(); ++j){
        if(idx[j].empty()) continue;
        if(t <= val[j].back())
            break;
    }
    if(j == (int)idx.size()){
        j--;
        idx.back().push_back(i);
        val.back().push_back(t);

        calc_p(j);
        mp[i] = j;
        return;
    }
    for(int k = 0; k < idx[j].size(); ++k){
        if(t <= val[j][k]){
            idx[j].insert(idx[j].begin() + k, i);
            val[j].insert(val[j].begin() + k, t);
            break;
        }
    }
    calc_p(j);
    mp[i] = j;
}

int cnt_upd = 0;
int update(int i, int y){
    if(cnt_upd++ % k_B == k_B - 1) 
        rebuild();

    remove(x[i], i);
    x[i] = y;
    add(x[i], i);

    return get_ans();    
}

/*
4 4 3
3 4 6 7
0 5 1
3 9 2
3 8 1
*/

Compilation message (stderr)

elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < idx.size(); ++i)
                    ~~^~~~~~~~~~~~
elephants.cpp: In function 'int get_ans()':
elephants.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < idx.size(); ++i){
                    ~~^~~~~~~~~~~~
elephants.cpp: In function 'void calc_p(int)':
elephants.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ptr == idx[i].size())
            ~~~~^~~~~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild()':
elephants.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < idx.size(); ++i){
                    ~~^~~~~~~~~~~~
elephants.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < val_tmp.size(); ++i){
                    ~~^~~~~~~~~~~~~~~~
elephants.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < idx.size(); ++i)
                    ~~^~~~~~~~~~~~
elephants.cpp: In function 'void remove(int, int)':
elephants.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = 0; k < idx[j].size(); ++k){
                    ~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j = 0; j < idx.size(); ++j){
                ~~^~~~~~~~~~~~
elephants.cpp:123:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = 0; k < idx[j].size(); ++k){
                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3