oj.uz

Submission #837316

# Submission time Handle Problem Language Result Execution time Memory
837316 2023-08-25T09:33:22 Z borisAngelov Sails (IOI07_sails) C++17
100 / 100
 75 ms 2788 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 548 KB Output is correct
2 Correct 18 ms 968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1112 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1544 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2312 KB Output is correct
2 Correct 46 ms 2400 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2528 KB Output is correct
2 Correct 36 ms 2132 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2788 KB Output is correct
2 Correct 46 ms 2376 KB Output is correct