oj.uz

Submission #387354

# Submission time Handle Problem Language Result Execution time Memory
387354 2021-04-08T09:47:35 Z Aldas25 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4353 ms 16484 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][2*510];
int j[510][2*510]; /// kiek kameru reiks, jei nuo kazkurio pradedam
int to[510][2*510]; /// kur tada baigsis intervalas visas
int last[510][2*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 (ids[b][t] - 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] = 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 (ids[b][sz[b]-1] - lst <= 0) continue;

        int le = 0, ri = sz[b]-1;
        while (le < ri) {
            int mid = (le+ri)/2;
            if (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 (ids[b][0] > x[id]) break;
            lst = b;
        }
    }
    //int lst = inBucket[id];

    bool was = false;
    for (int i = 0; i < sz[lst]-1; i++) {
        if (ids[lst][i] >= x[id]) was= true;
        if (!was) continue;
        //if (x[ids[lst][i]] < x[id]) continue;
        swap(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 (ids[b][0] > x[id]) break;
            lst = b;
        }
    }
    inBucket[id] = lst;

    ids[lst][sz[lst]] = x[id];
    for (int i = sz[lst]; i > 0; i--)
        if (ids[lst][i-1] > ids[lst][i])
            swap(ids[lst][i-1], ids[lst][i]);

    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]);
        x[i] = X[i];
        srt.pb(x[i]);
    }

    //for (int id : srt)cout << "   " << id;
    //cout << endl;

    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();
}

/*

3 10 3
50
61
71
2 61 2
1 50 2
0 40 2

4 10 6
0
0
0
0
0 10 1
0 0 1
2 11 2
0 11 2
1 11 2
3 11 1

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

2 1 5
50
50
0 49 1
0 50 1
1 48 2
0 49 1
0 47 1

*/

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 3 ms 2412 KB Output is correct
3 Correct 3 ms 2412 KB Output is correct
4 Correct 3 ms 2540 KB Output is correct
5 Correct 2 ms 2568 KB Output is correct
6 Correct 2 ms 2412 KB Output is correct
7 Correct 246 ms 4908 KB Output is correct
8 Correct 304 ms 5412 KB Output is correct
9 Correct 412 ms 6888 KB Output is correct
10 Correct 396 ms 6900 KB Output is correct
11 Correct 338 ms 6960 KB Output is correct
12 Correct 681 ms 6888 KB Output is correct
13 Correct 431 ms 6904 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 3 ms 2412 KB Output is correct
3 Correct 3 ms 2412 KB Output is correct
4 Correct 3 ms 2540 KB Output is correct
5 Correct 2 ms 2568 KB Output is correct
6 Correct 2 ms 2412 KB Output is correct
7 Correct 246 ms 4908 KB Output is correct
8 Correct 304 ms 5412 KB Output is correct
9 Correct 412 ms 6888 KB Output is correct
10 Correct 396 ms 6900 KB Output is correct
11 Correct 338 ms 6960 KB Output is correct
12 Correct 681 ms 6888 KB Output is correct
13 Correct 431 ms 6904 KB Output is correct
14 Correct 311 ms 5496 KB Output is correct
15 Correct 565 ms 5996 KB Output is correct
16 Correct 1043 ms 7144 KB Output is correct
17 Correct 1202 ms 7960 KB Output is correct
18 Correct 1322 ms 7956 KB Output is correct
19 Correct 751 ms 7968 KB Output is correct
20 Correct 1175 ms 9740 KB Output is correct
21 Correct 1204 ms 9700 KB Output is correct
22 Correct 712 ms 9336 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 3 ms 2412 KB Output is correct
3 Correct 3 ms 2412 KB Output is correct
4 Correct 3 ms 2540 KB Output is correct
5 Correct 2 ms 2568 KB Output is correct
6 Correct 2 ms 2412 KB Output is correct
7 Correct 246 ms 4908 KB Output is correct
8 Correct 304 ms 5412 KB Output is correct
9 Correct 412 ms 6888 KB Output is correct
10 Correct 396 ms 6900 KB Output is correct
11 Correct 338 ms 6960 KB Output is correct
12 Correct 681 ms 6888 KB Output is correct
13 Correct 431 ms 6904 KB Output is correct
14 Correct 311 ms 5496 KB Output is correct
15 Correct 565 ms 5996 KB Output is correct
16 Correct 1043 ms 7144 KB Output is correct
17 Correct 1202 ms 7960 KB Output is correct
18 Correct 1322 ms 7956 KB Output is correct
19 Correct 751 ms 7968 KB Output is correct
20 Correct 1175 ms 9740 KB Output is correct
21 Correct 1204 ms 9700 KB Output is correct
22 Correct 712 ms 9336 KB Output is correct
23 Correct 3469 ms 16352 KB Output is correct
24 Correct 3635 ms 16356 KB Output is correct
25 Correct 3429 ms 16292 KB Output is correct
26 Correct 3458 ms 16296 KB Output is correct
27 Correct 3537 ms 16348 KB Output is correct
28 Correct 616 ms 8080 KB Output is correct
29 Correct 565 ms 8020 KB Output is correct
30 Correct 610 ms 8044 KB Output is correct
31 Correct 577 ms 8044 KB Output is correct
32 Correct 2342 ms 15756 KB Output is correct
33 Correct 1794 ms 15232 KB Output is correct
34 Correct 2677 ms 16104 KB Output is correct
35 Correct 1679 ms 16484 KB Output is correct
36 Correct 1174 ms 15712 KB Output is correct
37 Correct 3264 ms 16096 KB Output is correct
38 Correct 2738 ms 15248 KB Output is correct
39 Correct 2482 ms 16112 KB Output is correct
40 Correct 2694 ms 15200 KB Output is correct
41 Correct 4174 ms 15712 KB Output is correct
42 Correct 4353 ms 15968 KB Output is correct