Submission #387276

#	Time	Username	Problem	Language	Result	Execution time	Memory
387276		Aldas25	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	778 ms	4200 KiB

elephants

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
typedef vector<int> vi;

const int MAXN = 500100;

int n, l;
//set<int> pos;
//map<int, int> cnt;
int x[MAXN];
int c;
vi srt;
int qCnt = 0;

int inBucket[MAXN];
int ids[510][510];
int j[510][510]; /// kiek kameru reiks, jei nuo kazkurio pradedam
int to[510][510]; /// kur tada baigsis intervalas visas
int last[510][510]; /// paskutinis id to intervalo
int sz[510];
int bucketCnt = 0;

void updateBucket (int b) {
    int t = sz[b]-1;
    for (int i = sz[b]-1; i >= 0; i--) {
        while (x[ids[b][t]] - x[ids[b][i]] > l) {t--;}
        /// ant ids[b][t] dar patenka, jei dedam ant ids[b][i]
        if (t < sz[b]-1) {
            j[b][i] = j[b][t+1] + 1;
            last[b][i] = last[b][t+1];
        } else {
            j[b][i] = 1;
            last[b][i] = ids[b][i];
        }

        to[b][i] = x[last[b][i]] + l;

       // cout <<"  bucket b=" << b << " i = " << i << "  ids = " << ids[b][i] << " pos = " << x[ids[b][i]]
       // << "  j = " << j[b][i] << " last = " << last[b][i] << " to = " << to[b][i] << endl;
    }
}

void updateAll () {
//cout << " updating all" << endl;
    FOR(i, 0, bucketCnt-1) {
        FOR(j, 0, sz[i]-1) {
            srt.pb(ids[i][j]);
            ids[i][j] = -1;
        }
        sz[i] = 0;
    }

    bucketCnt = 0;

    int curBucket = 0;
    for (int id : srt) {
        if (sz[curBucket] >= c) {
            curBucket++;
        }
        int where = sz[curBucket];
        ids[curBucket][where] = id;
        sz[curBucket]++;
        inBucket[id] = curBucket;
    }
    bucketCnt = curBucket+1;

    srt.clear();

    FOR(i, 0, bucketCnt-1) {
        updateBucket (i);
    }
}

int countCameras () {
    int ret = 0;
    int lst = -l-5;
    FOR(b, 0, bucketCnt-1) {
        if (sz[b] == 0) continue;

        if (x[ids[b][sz[b]-1]] - lst <= 0) continue;

        int le = 0, ri = sz[b]-1;
        while (le < ri) {
            int mid = (le+ri)/2;
            if (x[ids[b][mid]] - lst > 0) ri = mid;
            else le = mid+1;
        }

        ret += j[b][le];
        lst = to[b][le];

    }

    return ret;
}

void rem (int id) {
   /* int lst = 0;
    for (int b = 0; b < bucketCnt; b++) {
        if (sz[b] > 0) {
            lst = b;
            break;
        }
    }
    for (int b = 0; b < bucketCnt; b++) {
        if (sz[b] > 0) {
            if (x[ids[b][0]] > x[id]) break;
            lst = b;
        }
    } */
    int lst = inBucket[id];

    for (int i = 0; i < sz[lst]-1; i++) {
        if (x[ids[lst][i]] < x[id]) continue;
        ids[lst][i] = ids[lst][i+1];
    }
    ids[lst][sz[lst]-1] = -1;
    sz[lst]--;


    updateBucket(lst);
}

void add (int id) {
    int lst = 0;
    for (int b = 0; b < bucketCnt; b++) {
        if (sz[b] > 0) {
            lst = b;
            break;
        }
    }
    for (int b = 0; b < bucketCnt; b++) {
        if (sz[b] > 0) {
            if (x[ids[b][0]] > x[id]) break;
            lst = b;
        }
    }
    inBucket[id] = lst;

    bool wasAdded = false;
    for (int i = sz[lst]; i > 0; i--) {
        if (x[ids[lst][i-1]] < x[id]) {
            ids[lst][i] = id;
            wasAdded = true;
            break;
        }
        ids[lst][i] = ids[lst][i-1];
    }
    if (!wasAdded)
        ids[lst][0] = id;

    sz[lst]++;

    updateBucket(lst);
}

void init(int N, int L, int X[])
{
    FOR(i,0,510-1) FOR(j, 0, 510-1) {
        ids[i][j] = -1;
    }
    n = N;
    c = sqrt(n);
    l = L;
    FOR(i, 0, N-1) {
       // cnt[X[i]]++;
        //pos.insert(X[i]);
        srt.pb(i);
        x[i] = X[i];
    }

    updateAll();
}

int update(int i, int y)
{
    qCnt++;
    if (qCnt > c) {
        updateAll();
        //cout << " updupd" << endl;
        qCnt = 0;
    }

   // cout << " removing i= " << i << endl;
    rem (i);
    x[i] = y;
   // cout << " adding i=" << i << endl;
    add (i);

    return countCameras();
}

/*

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


4 10 0
7
17
20
32


2 1 7
0
100
0 99 1
0 98 2
1 97 1
1 98 1
1 99 1
1 100 2
1 98 1

*/

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