oj.uz

Submission #351217

# Submission time Handle Problem Language Result Execution time Memory
351217 2021-01-19T16:33:20 Z idk321 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 13764 KB 
#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


const int N = 150000;
const int NS = 1000;
vector<int> bags [NS];
int el[N];
int cost[NS][NS * 2 + 5];
int up[NS][NS * 2 + 5];
int n;
int l;
int used;

void bagUp(int bag)
{
    auto cbag = bags[bag];
    int j = cbag.size() - 1;
    int i = j;
    while (i >= 0)
    {
        if (cbag[i] + l >= cbag[j])
        {
            cost[bag][i] = 1;
            up[bag][i] = cbag[i] + l;
        } else
        {
            while (cbag[j - 1] - cbag[i] > l) j--;
            cost[bag][i] = cost[bag][j] + 1;
            up[bag][i] = up[bag][j];
        }

        i--;
    }
}

void rem(int node)
{
    int bag;
    for (bag = 0; bag < NS; bag++)
    {
        if (!bags[bag].empty() && el[node] <= *bags[bag].rbegin())
        {
            break;
        }
    }
    auto it = lower_bound(bags[bag].begin(), bags[bag].end(), el[node]);
    bags[bag].erase(it);
    bagUp(bag);
}

void addTo(int node, int y, int bag)
{
    auto it = bags[bag].begin();
    while(it != bags[bag].end() && *it < y) it++;
    auto cur = bags[bag].insert(it, y);
    bagUp(bag);
}

void add(int node, int y)
{
    bool found = false;
    el[node] = y;
    int bag;
    for (bag = 0; bag < NS; bag++)
    {
        if (!bags[bag].empty() && y <= *bags[bag].rbegin())
        {
            break;
        }
    }
    if (bag == NS)
    {
         bag--;
    }
    addTo(node, y, bag);
}

void make()
{
    vector<int> all;
    for (auto bag : bags) for (int i : bag) all.push_back(i);


    int c = 0;
    for (int i = 0; i < NS; i++)
    {
        bags[i].clear();
        for (int j = 0; j < NS && c < n; j++, c++)
        {
            bags[i].push_back(all[c]);
        }
    }

    for (int bag = 0; bag < NS; bag++)
    {
        bagUp(bag);
    }
}

int get()
{
    //for (int i = 0; i < NS; i++)for (int j : bags[i]) cout <<i << " "<< j<< endl;
    int last = -1;
    int res = 0;
    for (int bag = 0; bag < NS; bag++)
    {
        auto cbag = bags[bag];
        auto it = upper_bound(cbag.begin(), cbag.end(), last);
        if (it != cbag.end())
        {
            int i = it - cbag.begin();
            //cout << cbag[i] << " " << cost[bag][i] << endl;
            res += cost[bag][i];
            last = up[bag][i];
        }
    }

    return res;
}

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    for (int i = 0; i < n; i++) bags[0].push_back(X[i]);
    for (int i = 0; i < n; i++) el[i] = X[i];
    make();
    used = 0;
}

int update(int ind, int y)
{
    if (used % NS == 0) make();
    rem(ind);
    add(ind, y);

    used++;
    return get();
}

Compilation message

elephants.cpp: In function 'void addTo(int, int, int)':
elephants.cpp:60:10: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   60 |     auto cur = bags[bag].insert(it, y);
      |          ^~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:66:10: warning: unused variable 'found' [-Wunused-variable]
   66 |     bool found = false;
      |          ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1029 ms 1716 KB Output is correct
8 Correct 1071 ms 3032 KB Output is correct
9 Correct 1242 ms 4776 KB Output is correct
10 Correct 1214 ms 4508 KB Output is correct
11 Correct 1134 ms 4472 KB Output is correct
12 Correct 1723 ms 5016 KB Output is correct
13 Correct 1252 ms 4460 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1029 ms 1716 KB Output is correct
8 Correct 1071 ms 3032 KB Output is correct
9 Correct 1242 ms 4776 KB Output is correct
10 Correct 1214 ms 4508 KB Output is correct
11 Correct 1134 ms 4472 KB Output is correct
12 Correct 1723 ms 5016 KB Output is correct
13 Correct 1252 ms 4460 KB Output is correct
14 Correct 1213 ms 3748 KB Output is correct
15 Correct 1576 ms 3812 KB Output is correct
16 Correct 2780 ms 5368 KB Output is correct
17 Correct 3027 ms 6528 KB Output is correct
18 Correct 3211 ms 6576 KB Output is correct
19 Correct 2151 ms 6808 KB Output is correct
20 Correct 3014 ms 6628 KB Output is correct
21 Correct 2906 ms 6984 KB Output is correct
22 Correct 2147 ms 6040 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1029 ms 1716 KB Output is correct
8 Correct 1071 ms 3032 KB Output is correct
9 Correct 1242 ms 4776 KB Output is correct
10 Correct 1214 ms 4508 KB Output is correct
11 Correct 1134 ms 4472 KB Output is correct
12 Correct 1723 ms 5016 KB Output is correct
13 Correct 1252 ms 4460 KB Output is correct
14 Correct 1213 ms 3748 KB Output is correct
15 Correct 1576 ms 3812 KB Output is correct
16 Correct 2780 ms 5368 KB Output is correct
17 Correct 3027 ms 6528 KB Output is correct
18 Correct 3211 ms 6576 KB Output is correct
19 Correct 2151 ms 6808 KB Output is correct
20 Correct 3014 ms 6628 KB Output is correct
21 Correct 2906 ms 6984 KB Output is correct
22 Correct 2147 ms 6040 KB Output is correct
23 Correct 8337 ms 13596 KB Output is correct
24 Execution timed out 9021 ms 13764 KB Time limit exceeded
25 Halted 0 ms 0 KB -