oj.uz

Submission #255364

# Submission time Handle Problem Language Result Execution time Memory
255364 2020-07-31T19:53:38 Z Sorting Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8928 ms 21176 KB 
#include "elephants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int k_N = 15e4 + 3;
const int k_B = 1000;
 
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 471 ms 2044 KB Output is correct
8 Correct 510 ms 2616 KB Output is correct
9 Correct 620 ms 5224 KB Output is correct
10 Correct 675 ms 5576 KB Output is correct
11 Correct 606 ms 5192 KB Output is correct
12 Correct 1190 ms 5720 KB Output is correct
13 Correct 636 ms 5236 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 471 ms 2044 KB Output is correct
8 Correct 510 ms 2616 KB Output is correct
9 Correct 620 ms 5224 KB Output is correct
10 Correct 675 ms 5576 KB Output is correct
11 Correct 606 ms 5192 KB Output is correct
12 Correct 1190 ms 5720 KB Output is correct
13 Correct 636 ms 5236 KB Output is correct
14 Correct 672 ms 3300 KB Output is correct
15 Correct 784 ms 3556 KB Output is correct
16 Correct 2024 ms 6140 KB Output is correct
17 Correct 2130 ms 8280 KB Output is correct
18 Correct 2298 ms 8276 KB Output is correct
19 Correct 908 ms 7452 KB Output is correct
20 Correct 2107 ms 8224 KB Output is correct
21 Correct 2001 ms 7868 KB Output is correct
22 Correct 988 ms 7348 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 471 ms 2044 KB Output is correct
8 Correct 510 ms 2616 KB Output is correct
9 Correct 620 ms 5224 KB Output is correct
10 Correct 675 ms 5576 KB Output is correct
11 Correct 606 ms 5192 KB Output is correct
12 Correct 1190 ms 5720 KB Output is correct
13 Correct 636 ms 5236 KB Output is correct
14 Correct 672 ms 3300 KB Output is correct
15 Correct 784 ms 3556 KB Output is correct
16 Correct 2024 ms 6140 KB Output is correct
17 Correct 2130 ms 8280 KB Output is correct
18 Correct 2298 ms 8276 KB Output is correct
19 Correct 908 ms 7452 KB Output is correct
20 Correct 2107 ms 8224 KB Output is correct
21 Correct 2001 ms 7868 KB Output is correct
22 Correct 988 ms 7348 KB Output is correct
23 Correct 4391 ms 15676 KB Output is correct
24 Correct 5099 ms 15840 KB Output is correct
25 Correct 3642 ms 15312 KB Output is correct
26 Correct 4037 ms 15204 KB Output is correct
27 Correct 3818 ms 15356 KB Output is correct
28 Correct 2220 ms 3096 KB Output is correct
29 Correct 2183 ms 3184 KB Output is correct
30 Correct 2239 ms 3008 KB Output is correct
31 Correct 2187 ms 2912 KB Output is correct
32 Correct 3604 ms 14924 KB Output is correct
33 Correct 3808 ms 15396 KB Output is correct
34 Correct 3673 ms 15112 KB Output is correct
35 Correct 3786 ms 15088 KB Output is correct
36 Correct 6377 ms 15116 KB Output is correct
37 Correct 6988 ms 21156 KB Output is correct
38 Correct 3735 ms 18760 KB Output is correct
39 Correct 3413 ms 19496 KB Output is correct
40 Correct 3894 ms 18528 KB Output is correct
41 Correct 8928 ms 20992 KB Output is correct
42 Correct 8928 ms 21176 KB Output is correct