Submission #1280693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280693		ngocphu	Sails (IOI07_sails)	C++20	100 / 100	68 ms	1948 KiB

sails

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxN = 1e5 + 4;

int n, mx = 0;
pair<int,int> a[maxN];
ll bit[maxN];

void update(int x, int v)
{
    for (; x <= mx; x += x & -x) bit[x] += v;
}

ll get(int x)
{
    ll res = 0;
    for (; x >= 1; x -= x & -x) res += bit[x];
    return res;
}

int fi(int r, int x)
{
    int l = 1, res = -1;

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

        if (get(m) < x)
        {
            res = m;
            r = m - 1;
        }
        else l = m + 1;
    }

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//     freopen("test.INP","r",stdin);
//     freopen("test.OUT","w",stdout);

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].first >> a[i].second;
        mx = max(mx, a[i].first);
    }

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        int h = a[i].first, k = a[i].second;
        int last = h - k + 1;
        ll val = get(last);

        int p1 = fi(h, val);
        int p2 = fi(h, val + 1);

        if (p1 != -1)
        {
            update(p1, 1);
            update(h + 1, -1);
            k = k - (h - p1 + 1);
        }

        update(p2, 1);
        update(p2 + k, -1);
    }


    ll ans = 0;
    for (int i = 1; i <= mx; ++i)
    {
        ll x = get(i);
        ans += 1ll * x * (x - 1) / 2;
    }

    cout << ans;

    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