oj.uz

Submission #136049

# Submission time Handle Problem Language Result Execution time Memory
136049 2019-07-24T16:24:54 Z evpipis Dancing Elephants (IOI11_elephants) C++11
100 / 100
 5187 ms 19896 KB 
//#define TEST

#ifndef TEST
#include "elephants.h"
#endif // TEST

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 15e4+4;
int n, l, k, rem;
int hel[len], old[len];

struct bucket{
    vector<int> vec;
    vector<ii> nex;

    void add(int v){
        vec.insert(lower_bound(vec.begin(), vec.end(), v), v);
        upd();
    }

    void del(int v){
        vec.erase(lower_bound(vec.begin(), vec.end(), v));
        upd();
    }

    void upd(){
        nex.resize(vec.size());
        for (int i = (int)vec.size()-1, j = vec.size(); i >= 0; i--){
            while (vec[i]+l+1 <= vec[j-1])
                j--;

            if (j == vec.size())
                nex[i] = mp(vec[i]+l+1, 1);
            else
                nex[i] = mp(nex[j].fi, nex[j].se+1);
        }
    }

    void print(){
        for (int i = 0; i < vec.size(); i++)
            printf("%d ", vec[i]);
        printf("\n");

        for (int i = 0; i < nex.size(); i++)
            printf("(%d, %d) ", nex[i].fi, nex[i].se);
        printf("\n");
    }
};

bucket data[len];

int fin(int v){
    int l = 0, r = (n+k-1)/k-1, ans = -1;
    //printf("l = %d, r = %d\n", l, r);
    if (data[r].vec.empty())
        r--;

    while (l <= r){
        int mid = (l+r)/2;
        if (data[mid].vec.back() >= v)
            ans = mid, r = mid-1;
        else
            l = mid+1;
    }

    //printf("first bucket that contains element >= %d: %d\n", v, ans);
    return ans;
}

int update(int pos, int val){
    data[fin(old[pos])].del(old[pos]);
    old[pos] = val;
    //printf("after del\n");
    int hey = fin(val);
    if (hey == -1)
        hey = (n+k-1)/k-1;
    data[hey].add(val);
    rem--;
    //printf("after add\n");

    /*printf("rem = %d, buckets =\n", rem);
    for (int i = 0; i*k < n; i++){
        printf("bucket %d:\n", i);
        data[i].print();
    }*/

    //system("pause");

    if (rem == 0){
        for (int i = 0, x = 0; i*k < n; i++){
            for (int j = 0; j < data[i].vec.size(); j++)
                hel[x++] = data[i].vec[j];
            data[i].vec.clear();
        }

        for (int i = 0; i*k < n; i++){
            for (int j = i*k; j < min(n, (i+1)*k); j++)
                data[i].vec.pb(hel[j]);
            data[i].upd();
        }

        rem = k-1;
    }

    /*printf("buckets after refresh\n");
    for (int i = 0; i*k < n; i++){
        printf("bucket %d:\n", i);
        data[i].print();
    }*/

    int ans = 0, cur = 0;
    while (true){
        int b = fin(cur);
        if (b == -1)
            break;

        int p = lower_bound(data[b].vec.begin(), data[b].vec.end(), cur)-data[b].vec.begin();
        ans += data[b].nex[p].se;
        cur = data[b].nex[p].fi;
    }

    return ans;
}

void init(int N, int L, int xs[]) {
    n = N, l = L, k = 1606, rem = k-1; //1606;

    for (int i = 0; i < n; i++)
        old[i] = xs[i];

    //printf("bef\n");
    for (int i = 0; i*k < n; i++){
        for (int j = i*k; j < min((i+1)*k, n); j++)
            data[i].vec.pb(xs[j]);
        data[i].upd();
    }

    //printf("after build\n");

    /*for (int i = 0; i*k < n; i++){
        printf("bucket %d:\n", i);
        data[i].print();
    }*/
}

#ifdef TEST
int main(){
    int N, L, xs[len], M;
    scanf("%d %d %d", &N, &L, &M);
    for (int i = 0; i < N; i++)
        scanf("%d", &xs[i]);

    init(N, L, xs);

    for (int i = 0; i < M; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", update(a, b));
    }
    return 0;
}
#endif

Compilation message

elephants.cpp: In member function 'void bucket::upd()':
elephants.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j == vec.size())
                 ~~^~~~~~~~~~~~~
elephants.cpp: In member function 'void bucket::print()':
elephants.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < vec.size(); i++)
                         ~~^~~~~~~~~~~~
elephants.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < nex.size(); i++)
                         ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:99:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < data[i].vec.size(); j++)
                             ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 1056 ms 9716 KB Output is correct
8 Correct 1109 ms 9796 KB Output is correct
9 Correct 562 ms 11144 KB Output is correct
10 Correct 362 ms 10616 KB Output is correct
11 Correct 403 ms 10488 KB Output is correct
12 Correct 1225 ms 11384 KB Output is correct
13 Correct 489 ms 10460 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 1056 ms 9716 KB Output is correct
8 Correct 1109 ms 9796 KB Output is correct
9 Correct 562 ms 11144 KB Output is correct
10 Correct 362 ms 10616 KB Output is correct
11 Correct 403 ms 10488 KB Output is correct
12 Correct 1225 ms 11384 KB Output is correct
13 Correct 489 ms 10460 KB Output is correct
14 Correct 729 ms 10572 KB Output is correct
15 Correct 1556 ms 10488 KB Output is correct
16 Correct 2334 ms 11896 KB Output is correct
17 Correct 2024 ms 12828 KB Output is correct
18 Correct 2283 ms 12868 KB Output is correct
19 Correct 843 ms 12252 KB Output is correct
20 Correct 2007 ms 13044 KB Output is correct
21 Correct 1847 ms 12920 KB Output is correct
22 Correct 945 ms 11640 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 1056 ms 9716 KB Output is correct
8 Correct 1109 ms 9796 KB Output is correct
9 Correct 562 ms 11144 KB Output is correct
10 Correct 362 ms 10616 KB Output is correct
11 Correct 403 ms 10488 KB Output is correct
12 Correct 1225 ms 11384 KB Output is correct
13 Correct 489 ms 10460 KB Output is correct
14 Correct 729 ms 10572 KB Output is correct
15 Correct 1556 ms 10488 KB Output is correct
16 Correct 2334 ms 11896 KB Output is correct
17 Correct 2024 ms 12828 KB Output is correct
18 Correct 2283 ms 12868 KB Output is correct
19 Correct 843 ms 12252 KB Output is correct
20 Correct 2007 ms 13044 KB Output is correct
21 Correct 1847 ms 12920 KB Output is correct
22 Correct 945 ms 11640 KB Output is correct
23 Correct 3258 ms 18912 KB Output is correct
24 Correct 3880 ms 19124 KB Output is correct
25 Correct 2203 ms 18548 KB Output is correct
26 Correct 2359 ms 18040 KB Output is correct
27 Correct 3754 ms 17800 KB Output is correct
28 Correct 5145 ms 12408 KB Output is correct
29 Correct 5089 ms 12408 KB Output is correct
30 Correct 5153 ms 12356 KB Output is correct
31 Correct 5120 ms 12408 KB Output is correct
32 Correct 2433 ms 17452 KB Output is correct
33 Correct 1344 ms 16632 KB Output is correct
34 Correct 1760 ms 17524 KB Output is correct
35 Correct 1797 ms 19896 KB Output is correct
36 Correct 1217 ms 17272 KB Output is correct
37 Correct 3131 ms 19460 KB Output is correct
38 Correct 3175 ms 16612 KB Output is correct
39 Correct 2801 ms 17628 KB Output is correct
40 Correct 3158 ms 16632 KB Output is correct
41 Correct 4975 ms 19064 KB Output is correct
42 Correct 5187 ms 19336 KB Output is correct