Submission #386915

#	Time	Username	Problem	Language	Result	Execution time	Memory
386915		Aldas25	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9060 ms	3128 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)

const int MAXN = 500100;

int n, l;
set<int> pos;
map<int, int> cnt;
int x[MAXN];

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    FOR(i, 0, N-1) {
        cnt[X[i]]++;
        pos.insert(X[i]);
        x[i] = X[i];
    }
}

int update(int i, int y)
{
    cnt[x[i]]--;
    if (cnt[x[i]] == 0) pos.erase(x[i]);
    x[i] = y;
    cnt[x[i]]++;
    pos.insert(x[i]);

    int lstSt = -l-5;
    int ret = 0;
    //cout << " --" << endl;
    while (lstSt <= 1e9) {
        auto it = pos.upper_bound(lstSt+l);
        if (it == pos.end()) break;
        int p = *it;
        lstSt = p;
        ret++;
      //  cout << "lstSt = " << lstSt << endl;
    }

    return ret;

}

/*

4 10 5
10
15
17
20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3


*/

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