제출 #256169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256169		SamAnd	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	8102 ms	12768 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 = 150005;
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]));
    int k = 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);

        while (v[i][k - 1] > x + d)
            --k;

        if (k == sz(v[i]))
        {
            q[i][j] = 1;
            u[i][j] = x + d;
        }
        else
        {
            q[i][j] = 1 + q[i][k];
            u[i][j] = u[i][k];
        }
    }
}

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 qq;
int sx[N];

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

    for (int i = 0; i < S; ++i)
    {
        if (binary_search(all(v[i]), xx))
        {
            vector<int> vv;
            for (int j = 0; j < sz(v[i]); ++j)
            {
                if (v[i][j] == xx)
                {
                    for (int k = 0; k < j; ++k)
                        vv.push_back(v[i][k]);
                    for (int k = j + 1; k < sz(v[i]); ++k)
                        vv.push_back(v[i][k]);
                    break;
                }
            }
            v[i] = vv;
            clc(i);
            break;
        }
    }

    x[i] = y;

    bool z = false;
    for (int i = 0; i < S; ++i)
    {
        if (v[i].empty())
            continue;
        if (y < v[i][0])
        {
            reverse(all(v[i]));
            v[i].push_back(y);
            reverse(all(v[i]));
            clc(i);
            z = true;
            break;
        }
        if (y <= v[i].back())
        {
            vector<int> vv;
            for (int j = 0; j < sz(v[i]); ++j)
            {
                if (y <= v[i][j])
                {
                    for (int k = 0; k < j; ++k)
                        vv.push_back(v[i][k]);
                    vv.push_back(y);
                    for (int k = j; k < sz(v[i]); ++k)
                        vv.push_back(v[i][k]);
                    break;
                }
            }
            v[i] = vv;
            clc(i);
            z = true;
            break;
        }
    }

    if (!z)
    {
        v[S - 1].push_back(y);
        clc(S - 1);
    }

    if (qq % S == 0)
    {
        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: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3