제출 #255361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255361		Sorting	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	30 ms	3192 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int k_N = 15e4 + 3;
const int k_B = 500;
 
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.resize(idx.size());
}

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);

    /*cout << "idx: " << endl;
    for(auto t: idx){
        for(auto x: t)
            cout << x << " ";
        cout << endl;
    }
    cout << "val: " << endl;
    for(auto t: val){
        for(auto x: t)
            cout << x << " ";
        cout << endl;
    }
    cout << "p: " << endl;
    for(auto t: p){
        for(auto x: t)
            cout << x[0] << "," << x[1] << " ";
        cout << endl;
    }*/

    return get_ans();    
}

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

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'int get_ans()':
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 'void calc_p(int)':
elephants.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ptr == idx[i].size())
            ~~~~^~~~~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild()':
elephants.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < idx.size(); ++i){
                    ~~^~~~~~~~~~~~
elephants.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < val_tmp.size(); ++i){
                    ~~^~~~~~~~~~~~~~~~
elephants.cpp:85: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:91: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:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j = 0; j < idx.size(); ++j){
                ~~^~~~~~~~~~~~
elephants.cpp:117: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: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3