제출 #638314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638314		finn__	Sails (IOI07_sails)	C++17	40 / 100	60 ms	4368 KiB

sails

#include <bits/stdc++.h>
using namespace std;

struct segtree
{
    vector<long> t;
    size_t l;

    segtree(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        t = vector<long>(2 * l, 0);
    }

    void update_add(size_t i, long x)
    {
        i += l;
        t[i] += x;
        while (i > 1)
        {
            i >>= 1;
            t[i] = t[2 * i] + t[2 * i + 1];
        }
    }

    void range_incr(size_t i, size_t j)
    {
        update_add(i, 1);
        if (j < l - 1)
            update_add(j + 1, -1);
    }

    long prefix_sum(size_t i)
    {
        i += l;
        size_t j = l;
        long x = 0;

        while (j <= i)
        {
            if (j & 1)
                x += t[j++];
            if (!(i & 1))
                x += t[i--];
            i >>= 1;
            j >>= 1;
        }

        return x;
    }

    size_t nonzero_left(size_t const i)
    {
        size_t j = i + l;
        if (t[j])
            return i;
        size_t a = j, b = j;

        while (j > 1 && ((a + b) / 2 >= i + l || !t[2 * j]))
        {
            if (j & 1)
                a -= (b - a + 1);
            else
                b += (b - a + 1);
            j >>= 1;
        }

        if (!t[2 * j])
            return SIZE_MAX;

        j *= 2;
        while (j < l)
            j = (t[2 * j + 1] ? 2 * j + 1 : 2 * j);

        return j - l;
    }

    size_t nonzero_right(size_t const i)
    {
        size_t j = i + l;
        if (t[j])
            return i;
        size_t a = j, b = j;

        while (j > 1 && ((a + b + 1) / 2 <= i + l || !t[2 * j + 1]))
        {
            if (j & 1)
                a -= (b - a + 1);
            else
                b += (b - a + 1);
            j >>= 1;
        }

        if (!t[2 * j + 1])
            return SIZE_MAX;

        j = j * 2 + 1;
        while (j < l)
            j = (t[2 * j] ? 2 * j : 2 * j + 1);

        return j - l;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    cin >> n;

    vector<pair<size_t, size_t>> masts(n);
    size_t hmax = 0;
    for (auto &[h, k] : masts)
    {
        cin >> h >> k;
        hmax = max(hmax, h);
    }
    sort(masts.begin(), masts.end());

    segtree tree(hmax + 2);
    tree.range_incr(1, masts.begin()->second);

    for (auto it = ++masts.begin(); it != masts.end(); it++)
    {
        size_t h = it->first, k = it->second;

        size_t p = h - k + 1;
        size_t x = tree.nonzero_left(p);
        size_t y = tree.nonzero_right(p);

        if (y != p)
            tree.range_incr(x, x + (y - p - 1));
        if (y != SIZE_MAX)
            tree.range_incr(y, h);
    }

    size_t total_num = 0;
    for (size_t i = 1; i < hmax + 1; i++)
    {
        long x = tree.prefix_sum(i);
        total_num += x * (x - 1) / 2;
    }

    cout << total_num << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10