Submission #770485

#	Time	Username	Problem	Language	Result	Execution time	Memory
770485		adrilen	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	14 ms	2148 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>;

constexpr int maxn = 1.5e5, min_size = 20, max_size = 80, start_size = 150, num_groups = 1000;

int n, l;

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

    void calc()
    {
        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)
    {
        pos.emplace_back(p);
        n++;
        if (up) calc();
    }

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

        if (up) calc();
    }

} ;

Group groups[num_groups];

int get_total()
{
    int output = 0;

    int last_length = -1;
    for (int i = 0; i < num_groups; i++)
    {
        if (groups[i].n == 0) break;
        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[])
{
    n = N, l = L;

    for (int i = 0; i < n; i++) ind_to_pos[i] = X[i];


    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]);
        }
    }


    for (int y = 0; y < num_groups; y++)
    {
        if (groups[y].n == 0) break;
        groups[y].calc();
    }

}



int update(int i, int y)
{
    
    int u = ind_to_pos[i]; // Now position

    int j;
    for (j = 0; groups[j].pos.back() < u && groups[j + 1].n != 0; j++) ;
    
    groups[j].erase(u, true);

    ind_to_pos[i] = y;

    for (j = 0; groups[j].pos.back() < y && groups[j + 1].n != 0; j++);

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

    // for (int o = 0; o <= groups[j].n; o++)
    // {
    //     cout << groups[j].pref[o][0] << " " << groups[j].pref[o][1] << "\t";
    // }
    // cout << endl;
    return get_total();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3