oj.uz

Submission #387276

# Submission time Handle Problem Language Result Execution time Memory
387276 2021-04-08T08:24:09 Z Aldas25 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 778 ms 4200 KB 
#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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1388 KB Output is correct
2 Correct 2 ms 1388 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct
7 Correct 277 ms 2924 KB Output is correct
8 Correct 359 ms 3236 KB Output is correct
9 Correct 520 ms 4200 KB Output is correct
10 Correct 519 ms 4200 KB Output is correct
11 Correct 410 ms 4200 KB Output is correct
12 Correct 778 ms 4200 KB Output is correct
13 Correct 541 ms 4200 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1388 KB Output is correct
2 Correct 2 ms 1388 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct
7 Correct 277 ms 2924 KB Output is correct
8 Correct 359 ms 3236 KB Output is correct
9 Correct 520 ms 4200 KB Output is correct
10 Correct 519 ms 4200 KB Output is correct
11 Correct 410 ms 4200 KB Output is correct
12 Correct 778 ms 4200 KB Output is correct
13 Correct 541 ms 4200 KB Output is correct
14 Incorrect 112 ms 3512 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1388 KB Output is correct
2 Correct 2 ms 1388 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct
7 Correct 277 ms 2924 KB Output is correct
8 Correct 359 ms 3236 KB Output is correct
9 Correct 520 ms 4200 KB Output is correct
10 Correct 519 ms 4200 KB Output is correct
11 Correct 410 ms 4200 KB Output is correct
12 Correct 778 ms 4200 KB Output is correct
13 Correct 541 ms 4200 KB Output is correct
14 Incorrect 112 ms 3512 KB Output isn't correct
15 Halted 0 ms 0 KB -