제출 #255609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255609		SamAnd	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	0 / 100	109 ms	194040 KiB

elephants

#include "elephants.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;

int n, d;
int x[N];

struct ban
{
    int ans;
    int lx, rx;
    int ld, rd;
    ban()
    {
        ans = 0;
        lx = rx = 0;
        ld = rd = 0;
    }
    ban(int x)
    {
        ans = 1;
        lx = rx = x;
        ld = rd = 0;
    }
};

ban mer(const ban& l, const ban& r)
{
    if (l.ans == 0)
        return r;
    if (r.ans == 0)
        return l;

    ban res;

    res.ans = l.ans + r.ans;

    res.lx = l.lx;
    res.rx = r.rx;

    if ((r.lx - l.rx) > d)
    {
        res.ld = l.ld;
        res.rd = r.rd;
    }
    else
    {
        if (l.rd == 0)
            res.ans -= 1;
        else
            res.ans -= (l.rd / d + !!(l.rd % d));
        if (r.ld == 0)
            res.ans -= 1;
        else
            res.ans -= (r.ld / d + !!(r.ld % d));

        int dd = l.rd + r.lx - l.rx + r.ld;
        res.ans += (dd / d + !!(dd % d));

        if (l.rx - l.rd == l.lx)
            res.ld = dd;
        else
            res.ld = l.ld;
        if (r.lx + r.ld == r.rx)
            res.rd = dd;
        else
            res.rd = r.rd;
    }

    return res;
}

int z = 1;
ban t[N * L];
int l0[N * L], r0[N * L];
int q[N * L];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        q[pos] += y;
        if (q[pos])
            t[pos] = ban(x);
        else
            t[pos] = ban();
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
    {
        if (!l0[pos])
            l0[pos] = ++z;
        ubd(tl, m, x, y, l0[pos]);
    }
    else
    {
        if (!r0[pos])
            r0[pos] = ++z;
        ubd(m + 1, tr, x, y, r0[pos]);
    }
    t[pos] = mer(t[l0[pos]], t[r0[pos]]);
}

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)
    //    ubd(1, M, x[i], 1, 1);
}

int update(int i, int y)
{
    //ubd(1, M, x[i], -1, 1);
    x[i] = y;
    //ubd(1, M, x[i], 1, 1);

    sort(x, x + n);
    int ans = 0;
    int u = -1;
    for (int i = 0; i < n; ++i)
    {
        if (x[i] <= u)
            continue;
        ++ans;
        u = x[i] + d;
    }
    return ans;
}

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