oj.uz

Submission #426365

# Submission time Handle Problem Language Result Execution time Memory
426365 2021-06-13T20:09:28 Z JeanBombeur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 7188 ms 6988 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 = (2000);

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 1708 ms 1536 KB Output is correct
8 Correct 1629 ms 1780 KB Output is correct
9 Correct 1384 ms 2708 KB Output is correct
10 Correct 1444 ms 2540 KB Output is correct
11 Correct 1348 ms 2584 KB Output is correct
12 Correct 2368 ms 2716 KB Output is correct
13 Correct 1491 ms 2516 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 1708 ms 1536 KB Output is correct
8 Correct 1629 ms 1780 KB Output is correct
9 Correct 1384 ms 2708 KB Output is correct
10 Correct 1444 ms 2540 KB Output is correct
11 Correct 1348 ms 2584 KB Output is correct
12 Correct 2368 ms 2716 KB Output is correct
13 Correct 1491 ms 2516 KB Output is correct
14 Correct 1948 ms 2156 KB Output is correct
15 Correct 2140 ms 2428 KB Output is correct
16 Correct 3829 ms 3476 KB Output is correct
17 Correct 3522 ms 3860 KB Output is correct
18 Correct 3814 ms 4076 KB Output is correct
19 Correct 1934 ms 3420 KB Output is correct
20 Correct 3599 ms 4048 KB Output is correct
21 Correct 3619 ms 4352 KB Output is correct
22 Correct 1945 ms 3460 KB Output is correct

Subtask #5
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 1708 ms 1536 KB Output is correct
8 Correct 1629 ms 1780 KB Output is correct
9 Correct 1384 ms 2708 KB Output is correct
10 Correct 1444 ms 2540 KB Output is correct
11 Correct 1348 ms 2584 KB Output is correct
12 Correct 2368 ms 2716 KB Output is correct
13 Correct 1491 ms 2516 KB Output is correct
14 Correct 1948 ms 2156 KB Output is correct
15 Correct 2140 ms 2428 KB Output is correct
16 Correct 3829 ms 3476 KB Output is correct
17 Correct 3522 ms 3860 KB Output is correct
18 Correct 3814 ms 4076 KB Output is correct
19 Correct 1934 ms 3420 KB Output is correct
20 Correct 3599 ms 4048 KB Output is correct
21 Correct 3619 ms 4352 KB Output is correct
22 Correct 1945 ms 3460 KB Output is correct
23 Correct 6098 ms 6412 KB Output is correct
24 Correct 7188 ms 6540 KB Output is correct
25 Correct 4677 ms 6584 KB Output is correct
26 Correct 6031 ms 6920 KB Output is correct
27 Correct 6310 ms 6988 KB Output is correct
28 Incorrect 47 ms 2244 KB Output isn't correct
29 Halted 0 ms 0 KB -