Submission #837316

#	Time	Username	Problem	Language	Result	Execution time	Memory
837316		borisAngelov	Sails (IOI07_sails)	C++17	100 / 100	75 ms	2788 KiB

sails

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000;

int n;
vector<pair<int, int>> mast;

struct fenwick_tree
{
    int tree[maxn + 5];

    void update(int pos, int delta)
    {
        for (int i = pos; i <= maxn; i += (i & (-i)))
        {
            tree[i] += delta;
        }
    }

    int query(int pos)
    {
        int result = 0;

        for (int i = pos; i >= 1; i -= (i & (-i)))
        {
            result += tree[i];
        }

        return result;
    }
};

fenwick_tree bit;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        cin >> x >> y;
        mast.push_back(make_pair(x, y));
    }

    sort(mast.begin(), mast.end());

    for (int i = 0; i < n; ++i)
    {
        int h = mast[i].first;
        int k = mast[i].second;

        int diff = h - k + 1;
        int curr = bit.query(diff);

        int l = diff;
        int r = h;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (bit.query(mid) >= curr)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        int ans = r;

        l = 1;
        r = diff;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (bit.query(mid) <= curr)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        int ans2 = l;

        bit.update(ans + 1, +1);
        bit.update(h + 1, -1);
        bit.update(ans2, +1);
        bit.update(ans2 + k - (h - ans), -1);
    }

    long long ans = 0;

    for (int i = 1; i <= maxn; ++i)
    {
        long long curr = bit.query(i);
        ans += (curr * (curr - 1)) / 2;
    }

    cout << ans << endl;

    return 0;
}

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