제출 #136049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136049		evpipis	코끼리 (Dancing Elephants) (IOI11_elephants)	C++11	100 / 100	5187 ms	19896 KiB

elephants

//#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

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

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3