oj.uz

Submission #255396

# Submission time Handle Problem Language Result Execution time Memory
255396 2020-07-31T21:21:31 Z Sorting Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8440 ms 19884 KB 
#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

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 0 ms 384 KB Output is correct
5 Correct 0 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 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 739 ms 2216 KB Output is correct
8 Correct 739 ms 2588 KB Output is correct
9 Correct 742 ms 5288 KB Output is correct
10 Correct 638 ms 5332 KB Output is correct
11 Correct 605 ms 5332 KB Output is correct
12 Correct 1418 ms 5896 KB Output is correct
13 Correct 592 ms 5328 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 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 739 ms 2216 KB Output is correct
8 Correct 739 ms 2588 KB Output is correct
9 Correct 742 ms 5288 KB Output is correct
10 Correct 638 ms 5332 KB Output is correct
11 Correct 605 ms 5332 KB Output is correct
12 Correct 1418 ms 5896 KB Output is correct
13 Correct 592 ms 5328 KB Output is correct
14 Correct 918 ms 2936 KB Output is correct
15 Correct 1083 ms 3240 KB Output is correct
16 Correct 2514 ms 6156 KB Output is correct
17 Correct 2388 ms 8240 KB Output is correct
18 Correct 2601 ms 8156 KB Output is correct
19 Correct 905 ms 7512 KB Output is correct
20 Correct 2464 ms 8408 KB Output is correct
21 Correct 2271 ms 8392 KB Output is correct
22 Correct 1002 ms 7676 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 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 739 ms 2216 KB Output is correct
8 Correct 739 ms 2588 KB Output is correct
9 Correct 742 ms 5288 KB Output is correct
10 Correct 638 ms 5332 KB Output is correct
11 Correct 605 ms 5332 KB Output is correct
12 Correct 1418 ms 5896 KB Output is correct
13 Correct 592 ms 5328 KB Output is correct
14 Correct 918 ms 2936 KB Output is correct
15 Correct 1083 ms 3240 KB Output is correct
16 Correct 2514 ms 6156 KB Output is correct
17 Correct 2388 ms 8240 KB Output is correct
18 Correct 2601 ms 8156 KB Output is correct
19 Correct 905 ms 7512 KB Output is correct
20 Correct 2464 ms 8408 KB Output is correct
21 Correct 2271 ms 8392 KB Output is correct
22 Correct 1002 ms 7676 KB Output is correct
23 Correct 4653 ms 15436 KB Output is correct
24 Correct 5211 ms 15996 KB Output is correct
25 Correct 3488 ms 19556 KB Output is correct
26 Correct 4054 ms 19884 KB Output is correct
27 Correct 3681 ms 19436 KB Output is correct
28 Correct 3138 ms 5108 KB Output is correct
29 Correct 3145 ms 4992 KB Output is correct
30 Correct 3185 ms 5064 KB Output is correct
31 Correct 3180 ms 4716 KB Output is correct
32 Correct 3276 ms 19552 KB Output is correct
33 Correct 3517 ms 18668 KB Output is correct
34 Correct 3305 ms 19620 KB Output is correct
35 Correct 3556 ms 19612 KB Output is correct
36 Correct 5514 ms 19036 KB Output is correct
37 Correct 6345 ms 18952 KB Output is correct
38 Correct 3203 ms 17792 KB Output is correct
39 Correct 2883 ms 17436 KB Output is correct
40 Correct 3314 ms 17772 KB Output is correct
41 Correct 8331 ms 18716 KB Output is correct
42 Correct 8440 ms 19304 KB Output is correct