제출 #426323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
426323		someone	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	26 / 100	20 ms	2116 KiB

elephants

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

struct Val {
    int i, val, nb, exces;

    bool operator <(const Val& other) const {
        return val < other.val;
    }
};

const int T = 1600, N = 150 * 1000, NB_BLOCS = 1000, INF = 1e9;

int n, len, pos[N];
set<Val> iBloc;
vector<Val> bloc[NB_BLOCS];

void recalcul(int i) {
    int t = bloc[i].size();
    for(int j = t-1, k = t; j > -1; j--) {
        while(k > 0 && bloc[i][j].val + len < bloc[i][k-1].val)
            k--;
        if(k == n) {
            bloc[i][j].nb = 1;
            bloc[i][j].exces = bloc[i][j].val + len;
        } else {
            bloc[i][j].nb = bloc[i][k].nb + 1;
            bloc[i][j].exces = bloc[i][k].exces;
        }
    }
}

void initialise() {
    iBloc.clear();
    sort(pos, pos + n);
    for(int i = 0, j = 0; i < n; i += T, j++) {
        if(i + T >= n)
            iBloc.insert({j, INF, 0, 0});
        else
            iBloc.insert({j, pos[i + T]-1, 0, 0});
        bloc[j].clear();
        for(int k = i; k < min(i + T, n); k++)
            bloc[j].push_back({k, pos[k], 0, 0});
        recalcul(j);
    }
}

void del(int i, int toDel) {
    int t = bloc[i].size();
    for(int j = 1; j < t; j++)
        if(bloc[i][j-1].i == toDel)
            swap(bloc[i][j-1], bloc[i][j]);
    bloc[i].pop_back();
    recalcul(i);
}

void add(int i, int toAdd) {
    bloc[i].push_back({toAdd, pos[toAdd], 0, 0});
    int t = bloc[i].size();
    for(int j = t-1; j > 0; j--)
        if(bloc[i][j].val < bloc[i][j-1].val)
            swap(bloc[i][j], bloc[i][j-1]);
        else
            j = 0;
    recalcul(i);
}

int dicho(int i, int deb, int fin, int obj) {
    if(deb + 1 == fin)
        return deb;
    int med = (deb + fin) / 2;
    if(bloc[i][med].val >= obj)
        return dicho(i, deb, med, obj);
    return dicho(i, med, fin, obj);
}

int update(int i, int y) {
    auto it = iBloc.lower_bound({0, pos[i], 0, 0});
    del((*it).i, i);
    pos[i] = y;
    it = iBloc.lower_bound({0, pos[i], 0, 0});
    add((*it).i, i);
    if(bloc[(*it).i].size() == 2*T)
        initialise();

    int nb = 0, pre = 0, t = iBloc.size();
    for(int j = 0; j < t; j++) {
        int sz = bloc[j].size();
        if(bloc[j].size() != 0 && pre < bloc[j].back().val) {
            int id = dicho(j, 0, sz, pre);
            nb += bloc[j][id].nb;
            pre = bloc[j][id].exces;
        }
    }
    return nb;
}

void init(int n1, int L, int X[]) {
    n = n1, len = L;
    for(int i = 0; i < n; i++)
        pos[i] = X[i];
    initialise();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3