Submission #770638

#	Time	Username	Problem	Language	Result	Execution time	Memory
770638		adrilen	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	4260 ms	12444 KiB

elephants

#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 = 100, 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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3