oj.uz

Submission #426363

# Submission time Handle Problem Language Result Execution time Memory
426363 2021-06-13T20:05:11 Z JeanBombeur Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5691 ms 13988 KB 
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include "elephants.h"
using namespace std;

const int INFINI = (1000 * 1000 * 1000 + 1);
const int MAX_ELEPHANTS = (150 * 1000);
const int LOG = (10);
const int SQRT = (1000);

int Positions[MAX_ELEPHANTS];

vector <int> Elephants[SQRT];

vector <pair <int, int>> Answer[SQRT];

int nbElephants, tailleIntervalle;

void UpdateBucket(int bucket) {
    int sz = Elephants[bucket].size();
    int droite = sz;
    for (int i = droite - 1; i >= 0; i --)
    {
        while (Elephants[bucket][droite - 1] > Elephants[bucket][i] + tailleIntervalle)
            droite --;
        if (droite == sz)
            Answer[bucket][i] = {1, Elephants[bucket][i] + tailleIntervalle};
        else
            Answer[bucket][i] = {1 + Answer[bucket][droite].first, Answer[bucket][droite].second};
    }
    return;
}

void Insert(int bucket, int val) {
    vector <int> nv;
    for (int a : Elephants[bucket])
    {
        if (a >= val)
        {
            nv.push_back(val);
            val = INFINI;
        }
        nv.push_back(a);
    }
    if (val < INFINI)
        nv.push_back(val);
    Elephants[bucket] = nv;
    Answer[bucket].push_back({0, 0});
    UpdateBucket(bucket);
    return;
}

void Remove(int bucket, int val) {
    vector <int> nv;
    for (int a : Elephants[bucket])
    {
        if (a == val)
            val = -1;
        else
            nv.push_back(a);
    }
    Elephants[bucket] = nv;
    UpdateBucket(bucket);
    return;
}

int FindNext(int bucket, int val) {
    int ans = -1;
    int sz = Elephants[bucket].size();
    for (int i = (1 << LOG); i > 0; i /= 2)
    {
        if (ans + i < sz && Elephants[bucket][ans + i] <= val)
            ans += i;
    }
    return ans + 1;
}

int FindAnswer() {
    int ans = 0;
    int curBucket = 0;
    int curId = 0;
    while (Elephants[curBucket].size() > 0)
    {
        ans += Answer[curBucket][curId].first;
        int saut = Answer[curBucket][curId].second;
        curId = FindNext(++ curBucket, saut);
        while (curId != 0 && curId == (int)Elephants[curBucket].size())
            curId = FindNext(++ curBucket, saut);
    }
    return ans;
}

void ResetBuckets() {
    vector <int> AllPos;
    int curBucket = 0;
    while (Elephants[curBucket].size() > 0)
    {
        for (int a : Elephants[curBucket])
            AllPos.push_back(a);
        curBucket ++;
    }
    for (int i = 0; i < curBucket; i ++)
    {
        Elephants[i].clear();
        Answer[i].clear();
    }
    curBucket = 0;
    for (int i = 0; i < nbElephants; i ++)
    {
        if ((int)Elephants[curBucket].size() > SQRT && (nbElephants - i) >= SQRT / 2)
            curBucket ++;
        Elephants[curBucket].push_back(AllPos[i]);
        Answer[curBucket].push_back({0, 0});
    }
    for (int i = 0; i <= curBucket; i ++)
    {
        UpdateBucket(i);
    }
    return;
}

void init(int N, int L, int X[]) {
    nbElephants = N;
    tailleIntervalle = L;
    for (int i = 0; i < nbElephants; i ++)
    {
        Positions[i] = X[i];
    }
    sort(X, X + nbElephants);
    int curBucket = 0;
    for (int i = 0; i < nbElephants; i ++)
    {
        if ((int)Elephants[curBucket].size() > SQRT && (nbElephants - i) >= SQRT / 2)
            curBucket ++;
        Elephants[curBucket].push_back(X[i]);
        Answer[curBucket].push_back({0, 0});
    }
    for (int i = 0; i <= curBucket; i ++)
    {
        UpdateBucket(i);
    }
    return;
}

int update(int id, int nouvPos) {
    
    int prev = Positions[id];
    Positions[id] = nouvPos;
    
    int curBucket = 0;
    bool reset = false;
    while ((int)Elephants[curBucket].size() > 0 && Elephants[curBucket].back() < prev)
        curBucket ++;
    if (Elephants[curBucket].size() == 0)
        curBucket --;
    Remove(curBucket, prev);
    if (Elephants[curBucket].size() == 1)
        reset = true;
    
    curBucket = 0;
    while ((int)Elephants[curBucket].size() > 0 && Elephants[curBucket].back() < nouvPos)
        curBucket ++;
    if (Elephants[curBucket].size() == 0)
        curBucket --;
    Insert(curBucket, nouvPos);
    if (Elephants[curBucket].size() >= 2 * SQRT)
        reset = true;
    
    if (reset)
        ResetBuckets();
    
    return FindAnswer();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 881 ms 1520 KB Output is correct
8 Correct 923 ms 1832 KB Output is correct
9 Correct 827 ms 2996 KB Output is correct
10 Correct 872 ms 2428 KB Output is correct
11 Correct 845 ms 2496 KB Output is correct
12 Correct 1349 ms 2748 KB Output is correct
13 Correct 846 ms 2468 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 881 ms 1520 KB Output is correct
8 Correct 923 ms 1832 KB Output is correct
9 Correct 827 ms 2996 KB Output is correct
10 Correct 872 ms 2428 KB Output is correct
11 Correct 845 ms 2496 KB Output is correct
12 Correct 1349 ms 2748 KB Output is correct
13 Correct 846 ms 2468 KB Output is correct
14 Correct 1130 ms 2240 KB Output is correct
15 Correct 1153 ms 2392 KB Output is correct
16 Correct 2179 ms 3460 KB Output is correct
17 Correct 2173 ms 4148 KB Output is correct
18 Correct 2259 ms 4308 KB Output is correct
19 Correct 1308 ms 3552 KB Output is correct
20 Correct 2103 ms 4264 KB Output is correct
21 Correct 2126 ms 3912 KB Output is correct
22 Correct 1298 ms 3584 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 881 ms 1520 KB Output is correct
8 Correct 923 ms 1832 KB Output is correct
9 Correct 827 ms 2996 KB Output is correct
10 Correct 872 ms 2428 KB Output is correct
11 Correct 845 ms 2496 KB Output is correct
12 Correct 1349 ms 2748 KB Output is correct
13 Correct 846 ms 2468 KB Output is correct
14 Correct 1130 ms 2240 KB Output is correct
15 Correct 1153 ms 2392 KB Output is correct
16 Correct 2179 ms 3460 KB Output is correct
17 Correct 2173 ms 4148 KB Output is correct
18 Correct 2259 ms 4308 KB Output is correct
19 Correct 1308 ms 3552 KB Output is correct
20 Correct 2103 ms 4264 KB Output is correct
21 Correct 2126 ms 3912 KB Output is correct
22 Correct 1298 ms 3584 KB Output is correct
23 Correct 4360 ms 7704 KB Output is correct
24 Correct 4939 ms 7744 KB Output is correct
25 Correct 3646 ms 8024 KB Output is correct
26 Correct 4189 ms 6856 KB Output is correct
27 Correct 4299 ms 6992 KB Output is correct
28 Correct 4027 ms 3800 KB Output is correct
29 Correct 3782 ms 6440 KB Output is correct
30 Correct 3955 ms 6716 KB Output is correct
31 Correct 3807 ms 6648 KB Output is correct
32 Correct 3691 ms 11268 KB Output is correct
33 Correct 3517 ms 10656 KB Output is correct
34 Correct 3857 ms 11520 KB Output is correct
35 Correct 3796 ms 13988 KB Output is correct
36 Correct 2599 ms 11760 KB Output is correct
37 Correct 4601 ms 12376 KB Output is correct
38 Correct 3690 ms 10516 KB Output is correct
39 Correct 3775 ms 11556 KB Output is correct
40 Correct 3713 ms 10536 KB Output is correct
41 Correct 5581 ms 13216 KB Output is correct
42 Correct 5691 ms 13516 KB Output is correct