oj.uz

Submission #56435

# Submission time Handle Problem Language Result Execution time Memory
56435 2018-07-11T10:30:50 Z aquablitz11 Dancing Elephants (IOI11_elephants) C++14
10 / 100
 9 ms 7876 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int N = 150010;
const int SN = 390;

int n, sn, l, X[N];
vector<int> elep[SN], cnt[N], rbnd[N];

int find_bucket(int x)
{
    for (int i = 0; i < sn; ++i) {
        if (x <= elep[i].back())
            return i;
    }
    return sn-1;
}

void process_bucket(int p)
{
    //fprintf(stderr, "process_bucket(%d):\n", p);
    int n = elep[p].size();
    cnt[p].resize(n);
    rbnd[p].resize(n);
    for (int i = n-1, j = n-1; i >= 0; --i) {
        while (elep[p][j]-elep[p][i] > l)
            --j;
        cnt[p][i] = j == n-1 ? 1 : (1 + cnt[p][j+1]);
        rbnd[p][i] = j == n-1 ? elep[p][i]+l : elep[p][j+1];
    }
    /*for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", elep[p][i]);
    }
    fprintf(stderr, "\n");
    for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", cnt[p][i]);
    }
    fprintf(stderr, "\n");
    for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", rbnd[p][i]);
    }
    fprintf(stderr, "\n");
    fprintf(stderr, "\n");*/
}

void process_all()
{
    //fprintf(stderr, "process_all():\n");
    vector<int> X(::X, ::X+n);
    sort(X.begin(), X.end());
    for (int i = 0; i < sn; ++i) {
        elep[i].clear();
        elep[i].reserve(3*sn);
    }
    for (int i = 0; i < n; ++i) {
        int b = i/sn;
        if (b >= sn) b = sn-1;
        elep[b].push_back(X[i]);
        //fprintf(stderr, "add elephant X = %d to block %d\n", X[i], b);
    }
    //fprintf(stderr, "\n");
    for (int i = 0; i < sn; ++i)
        process_bucket(i);
}

void init(int n, int l, int X[])
{
    ::n = n, ::l = l, ::sn = sqrt(n);
    for (int i = 0; i < n; ++i)
        ::X[i] = X[i];
    process_all();
}

int cnt_upd = 0;
bool skip = false;
int update(int i, int y)
{
    //fprintf(stderr, "update(%d, %d):\n", i, y);
    if (!skip && ((++cnt_upd) % sn == 0)) {
        X[i] = y;
        process_all();
    } else {
        int bx = find_bucket(X[i]);
        int by = find_bucket(y);
        elep[bx].erase(find(elep[bx].begin(), elep[bx].end(), X[i]));
        elep[by].insert(lower_bound(elep[by].begin(), elep[by].end(), y), y);
        //fprintf(stderr, "%d is in bucket %d, %d is in bucket %d\n", X[i], bx, y, by);
        process_bucket(bx);
        if (bx != by) process_bucket(by);
        X[i] = y;
    }
    //fprintf(stderr, "\n");

    int ans = 0, last = -1;
    for (int b = 0; b < sn; ++b) {
        int i = upper_bound(elep[b].begin(), elep[b].end(), last) - elep[b].begin();
        if (i < elep[b].size()) {
            //fprintf(stderr, "block %d, got elephant %d: %d %d %d\n", b, i, elep[b][i], cnt[b][i], rbnd[b][i]);
            ans += cnt[b][i];
            last = rbnd[b][i];
        }
    }

    return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < elep[b].size()) {
             ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Incorrect 9 ms 7876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Incorrect 9 ms 7876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Incorrect 9 ms 7876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Incorrect 9 ms 7876 KB Output isn't correct
5 Halted 0 ms 0 KB -