Submission #256147

#	Time	Username	Problem	Language	Result	Execution time	Memory
256147		SamAnd	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9027 ms	2176 KiB

elephants

#include "elephants.h"
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 300005, L = 33, M = 1000000000;
const int S = 400;

int n, d;
int x[N];

vector<int> v[S];
vector<int> q[S];
vector<int> u[S];

void clc(int i)
{
    q[i].resize(sz(v[i]));
    u[i].resize(sz(v[i]));
    for (int j = sz(v[i]) - 1; j >= 0; --j)
    {
        int x = v[i][j];
        auto it = upper_bound(all(v[i]), x + d);
        if (it == v[i].end())
        {
            q[i][j] = 1;
            u[i][j] = x + d;
        }
        else
        {
            q[i][j] = 1 + q[i][it - v[i].begin()];
            u[i][j] = u[i][it - v[i].begin()];
        }
    }
}

int ans()
{
    int qq = 0;
    int uu = -1;
    for (int i = 0; i < S; ++i)
    {
        auto it = upper_bound(all(v[i]), uu);
        if (it == v[i].end())
            continue;
        qq += q[i][it - v[i].begin()];
        uu = u[i][it - v[i].begin()];
    }
    return qq;
}

void init(int N, int L, int X[])
{
    n = N;
    d = L;
    for (int i = 0; i < n; ++i)
        x[i] = X[i];

    for (int i = 0; i < n; ++i)
    {
        v[(i / S)].push_back(x[i]);
    }

    for (int i = 0; i < S; ++i)
    {
        clc(i);
    }
}

int sx[N];

int update(int i, int y)
{
    x[i] = y;

    for (int i = 0; i < n; ++i)
        sx[i] = x[i];
    sort(sx, sx + n);
    for (int i = 0; i < S; ++i)
        v[i].clear();
    for (int i = 0; i < n; ++i)
        v[(i / S)].push_back(sx[i]);
    for (int i = 0; i < S; ++i)
        clc(i);

    return ans();
}

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