Submission #351205

#	Time	Username	Problem	Language	Result	Execution time	Memory
351205		idk321	Dancing Elephants (IOI11_elephants)	C++11	26 / 100	22 ms	3052 KiB

elephants

#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


const int N = 150000;
const int NS = 400;
vector<int> bags [NS];
int el[NS];
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 : bags[0]) cout << i<< 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 (stderr)

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