oj.uz

Submission #770640

# Submission time Handle Problem Language Result Execution time Memory
770640 2023-07-01T14:55:03 Z adrilen Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5362 ms 7260 KB 
#include "elephants.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

// Start = 100
constexpr int maxn = 1.5e5, start_size = 300, num_groups = maxn / start_size + 1;

int n, l;

struct Group {
    int n;
    vector <int> pos;
    vector <arr> pref;

    void calc()             // O(n log n)
    {
        assert(n == (int)pos.size());
        pref.resize(n + 1);

        pref[n] = {0, 0};
        sort(pos.begin(), pos.end());

        for (int p = n - 1; p >= 0; p--)
        {
            int ind = upper_bound(pos.begin(), pos.end(), pos[p] + l) - pos.begin();    
            
            pref[p] = {pref[ind][0] + 1, max(pos[p] + l, pref[ind][1])};
        }
    }

    void insert(int p, bool up = false)     // O(sqrt(n))
    {
        pos.emplace_back(p);
        n++;
        if (up) calc();
    }

    void erase(int p, bool up = false)      // O(sqrt(n))
    {
        n--;
        pos.erase(lower_bound(pos.begin(), pos.end(), p));

        if (up) calc();
    }

} ;

vector<Group> groups;


void split_group(int p)
{   
    Group ne = Group();

    ne.pos = vector<int>(groups[p].pos.begin() + groups[p].n / 2, groups[p].pos.end());

    // cout <<"aa\n";
    // for (int i : ne.pos) cout << i << " ";
    // cout << "\n";
    groups[p].pos.resize(groups[p].n / 2);
    groups[p].n /= 2;

    groups[p].calc();

    ne.n = ne.pos.size();
    ne.calc();

    groups.insert(groups.begin() + p + 1, ne);
}


void print_groups()
{
    for (int a = 0; a < (int)groups.size(); a++)
    {
        cout << a << " " << groups[a].n << " " << groups[a].pos.size() <<  "\n";
        for (int i : groups[a].pos) cout << i << "\t";
        cout << "\n";
        for (arr i : groups[a].pref) cout << i[0] << " " << i[1] << "\t";
        cout << "\n";

    }
    cout << endl;
}


int get_total()                         // O(n / sqrt(n) log n)
{
    int output = 0;

    int last_length = -1;
    for (int i = 0; i < (int)groups.size(); i++)
    {
        int pos = upper_bound(groups[i].pos.begin(), groups[i].pos.end(), last_length) - groups[i].pos.begin();

        output += groups[i].pref[pos][0];
        last_length = max(last_length, groups[i].pref[pos][1]);
    }

    return output;
}


int ind_to_pos[maxn] = { 0 };
void init(int N, int L, int X[])            // O(n / sqrt(n))
{
    n = N, l = L;
    
    for (int i = 0; i < n; i++) ind_to_pos[i] = X[i];


    groups.resize((n - 1) / start_size + 1);

    for (int y = 0; y <= n / start_size; y++)
    {
        for (int i = 0; i < start_size; i++)
        {
            if (y * start_size + i == n) {
                y = 2e9;
                break;
            }
            groups[y].insert(X[y * start_size + i]);
        }
    }
    // print_groups();

    int y;
    for (y = 0; y < (int)groups.size(); y++)
    {
        groups[y].calc();
    }
    assert((int)groups.size() == y);

    // print_groups();
}





int fnd_group(int p)
{
    int l = 0, r = groups.size() - 1, mid;

    while (l != r)
    {
        mid = (l + r) >> 1;

        if (groups[mid].pos.back() < p) l = mid + 1;
        else r = mid;
    }

    return l;
}

int q = 0;
int update(const int i, int y)
{
    // cout << "NEW QUERY\n";

    int u = ind_to_pos[i]; // Now position

    int j = fnd_group(u);

    groups[j].erase(u, true);

    if (groups[j].n == 0)
    {
        groups.erase(groups.begin() + j);
    }

    ind_to_pos[i] = y;

    j = fnd_group(y);
    groups[j].insert(y, true);


    if (groups[j].n >= start_size * 1.5) split_group(j);

    // print_groups();

    // q++;
    // if (q % 1000 == 0)
    // {
    //     for (int x = 0; x < groups.size(); x++)
    //     {
    //         cout << groups[x].n << " ";
    //     }
    //     cout << "\n";
    // }

    return get_total();
}


/*
g++ -o $PROBLEM grader.cpp $PROBLEM.cpp -fsanitize="address","undefined" -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -Wall -g3 -O2 && ./$PROBLEM
g++ -o $PROBLEM grader.cpp $PROBLEM.cpp -Wall -g3 && ./$PROBLEM


*/

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1215 ms 1208 KB Output is correct
8 Correct 1262 ms 1324 KB Output is correct
9 Correct 864 ms 2284 KB Output is correct
10 Correct 597 ms 2592 KB Output is correct
11 Correct 584 ms 2544 KB Output is correct
12 Correct 1388 ms 2456 KB Output is correct
13 Correct 566 ms 2576 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1215 ms 1208 KB Output is correct
8 Correct 1262 ms 1324 KB Output is correct
9 Correct 864 ms 2284 KB Output is correct
10 Correct 597 ms 2592 KB Output is correct
11 Correct 584 ms 2544 KB Output is correct
12 Correct 1388 ms 2456 KB Output is correct
13 Correct 566 ms 2576 KB Output is correct
14 Correct 815 ms 1900 KB Output is correct
15 Correct 1229 ms 1852 KB Output is correct
16 Correct 2179 ms 2700 KB Output is correct
17 Correct 2129 ms 3776 KB Output is correct
18 Correct 2122 ms 3144 KB Output is correct
19 Correct 1475 ms 2640 KB Output is correct
20 Correct 2185 ms 3824 KB Output is correct
21 Correct 2112 ms 3284 KB Output is correct
22 Correct 868 ms 3288 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1215 ms 1208 KB Output is correct
8 Correct 1262 ms 1324 KB Output is correct
9 Correct 864 ms 2284 KB Output is correct
10 Correct 597 ms 2592 KB Output is correct
11 Correct 584 ms 2544 KB Output is correct
12 Correct 1388 ms 2456 KB Output is correct
13 Correct 566 ms 2576 KB Output is correct
14 Correct 815 ms 1900 KB Output is correct
15 Correct 1229 ms 1852 KB Output is correct
16 Correct 2179 ms 2700 KB Output is correct
17 Correct 2129 ms 3776 KB Output is correct
18 Correct 2122 ms 3144 KB Output is correct
19 Correct 1475 ms 2640 KB Output is correct
20 Correct 2185 ms 3824 KB Output is correct
21 Correct 2112 ms 3284 KB Output is correct
22 Correct 868 ms 3288 KB Output is correct
23 Correct 4987 ms 6320 KB Output is correct
24 Correct 5132 ms 6364 KB Output is correct
25 Correct 3010 ms 6120 KB Output is correct
26 Correct 3478 ms 6884 KB Output is correct
27 Correct 4493 ms 5592 KB Output is correct
28 Correct 2987 ms 2252 KB Output is correct
29 Correct 2622 ms 2252 KB Output is correct
30 Correct 3030 ms 2332 KB Output is correct
31 Correct 2624 ms 2260 KB Output is correct
32 Correct 2520 ms 6752 KB Output is correct
33 Correct 2210 ms 6784 KB Output is correct
34 Correct 2457 ms 6768 KB Output is correct
35 Correct 2055 ms 5708 KB Output is correct
36 Correct 1890 ms 5484 KB Output is correct
37 Correct 4675 ms 7260 KB Output is correct
38 Correct 2349 ms 6992 KB Output is correct
39 Correct 3562 ms 5628 KB Output is correct
40 Correct 2262 ms 6812 KB Output is correct
41 Correct 5362 ms 7132 KB Output is correct
42 Correct 5329 ms 7052 KB Output is correct