oj.uz

Submission #638314

# Submission time Handle Problem Language Result Execution time Memory
638314 2022-09-05T09:24:32 Z finn__ Sails (IOI07_sails) C++17
40 / 100
 60 ms 4368 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 7 ms 2376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 980 KB Output is correct
2 Correct 13 ms 1108 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1572 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 2256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4028 KB Output is correct
2 Incorrect 37 ms 4368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 4080 KB Output isn't correct
2 Halted 0 ms 0 KB -