oj.uz

Submission #433479

# Submission time Handle Problem Language Result Execution time Memory
433479 2021-06-19T21:13:05 Z someone Dancing Elephants (IOI11_elephants) C++14
26 / 100
 1137 ms 4676 KB 
#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 = 1042, N = 150 * 1000 + 10, NB_BLOCS = 1000, INF = 1e9;

Val pos[N];
set<Val> iBloc;
int n, len, position[N];
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 == t) {
            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() {
    //cout << "INITIALIZE\n";
    iBloc.clear();
    sort(pos, pos + n);
    for(int i = 0; i < n; i++)
        position[pos[i].i] = i;
    for(int i = 0, j = 0; i < n; i += T, j++) {
        if(i + T >= n) {
            iBloc.insert({j, INF, 0, 0});
            //cout << j << '\n';
        } else
            iBloc.insert({j, pos[i + T].val-1, 0, 0});
        bloc[j].clear();
        for(int k = i; k < min(i + T, n); k++)
            bloc[j].push_back({k, pos[k].val, 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].val, 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;
    if(deb+2 == fin) {
        if(bloc[i][deb].val > obj)
            return deb;
        return deb+1;
    }
    int med = (deb + fin) / 2;
    if(bloc[i][med-1].val < obj)
        return dicho(i, med, fin, obj);
    return dicho(i, deb, med, obj);
}

int update(int i, int y) {
    /*for(Val v : iBloc)
        cout << v.val << ' ';
    cout << '\n';*/
    auto it = iBloc.lower_bound({0, pos[position[i]].val, 0, 0});
    //cout << (*it).i << '\n';

    del((*it).i, position[i]);
    pos[position[i]].val = y;
    it = iBloc.lower_bound({0, pos[position[i]].val, 0, 0});
    //cout << (*it).i << '\n';

    add((*it).i, position[i]);
    if(bloc[(*it).i].size() == 2*T)
        initialise();

    //cout << i << ' ' << y << '\n';
    int nb = 0, pre = -1, t = iBloc.size();
    for(int j = 0; j < t; j++) {
        int sz = bloc[j].size();
        //cout << pre << ' ' << bloc[j].back().val << ' ';
        if(bloc[j].size() != 0 && pre < bloc[j].back().val) {
            int id = dicho(j, 0, sz, pre);
            //cout << id << ' ' << bloc[j][id].val << ' ' << bloc[j][id+1].val << ' ';
            nb += bloc[j][id].nb;
            pre = bloc[j][id].exces;
        }
        //cout << nb << '\n';
    }
    //cout << '\n';
    return nb;
}

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

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1103 ms 2416 KB Output is correct
8 Correct 1137 ms 2720 KB Output is correct
9 Correct 744 ms 4676 KB Output is correct
10 Incorrect 45 ms 4420 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1103 ms 2416 KB Output is correct
8 Correct 1137 ms 2720 KB Output is correct
9 Correct 744 ms 4676 KB Output is correct
10 Incorrect 45 ms 4420 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1103 ms 2416 KB Output is correct
8 Correct 1137 ms 2720 KB Output is correct
9 Correct 744 ms 4676 KB Output is correct
10 Incorrect 45 ms 4420 KB Output isn't correct
11 Halted 0 ms 0 KB -