oj.uz

Submission #387328

# Submission time Handle Problem Language Result Execution time Memory
387328 2021-04-08T09:14:27 Z Aldas25 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 1147 ms 7140 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 (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;
        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();
}

/*

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 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 231 ms 3820 KB Output is correct
8 Correct 285 ms 4212 KB Output is correct
9 Correct 426 ms 5736 KB Output is correct
10 Correct 377 ms 5608 KB Output is correct
11 Correct 299 ms 5636 KB Output is correct
12 Correct 603 ms 5608 KB Output is correct
13 Correct 427 ms 5412 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 231 ms 3820 KB Output is correct
8 Correct 285 ms 4212 KB Output is correct
9 Correct 426 ms 5736 KB Output is correct
10 Correct 377 ms 5608 KB Output is correct
11 Correct 299 ms 5636 KB Output is correct
12 Correct 603 ms 5608 KB Output is correct
13 Correct 427 ms 5412 KB Output is correct
14 Correct 285 ms 5028 KB Output is correct
15 Correct 510 ms 5376 KB Output is correct
16 Correct 926 ms 6248 KB Output is correct
17 Correct 1033 ms 7140 KB Output is correct
18 Correct 1147 ms 7140 KB Output is correct
19 Incorrect 37 ms 6884 KB Output isn't correct
20 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 231 ms 3820 KB Output is correct
8 Correct 285 ms 4212 KB Output is correct
9 Correct 426 ms 5736 KB Output is correct
10 Correct 377 ms 5608 KB Output is correct
11 Correct 299 ms 5636 KB Output is correct
12 Correct 603 ms 5608 KB Output is correct
13 Correct 427 ms 5412 KB Output is correct
14 Correct 285 ms 5028 KB Output is correct
15 Correct 510 ms 5376 KB Output is correct
16 Correct 926 ms 6248 KB Output is correct
17 Correct 1033 ms 7140 KB Output is correct
18 Correct 1147 ms 7140 KB Output is correct
19 Incorrect 37 ms 6884 KB Output isn't correct
20 Halted 0 ms 0 KB -