Submission #1208083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208083		PakinDioxide	Sails (IOI07_sails)	C++17	5 / 100	22 ms	2632 KiB

sails

/*
    author  : PakinDioxide
    created : 26/05/2025 19:47
    task    : IOI07_sails
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e5+5;

int n;
pair <ll, ll> a[mxN];
ll fen[mxN], idx = LLONG_MAX, ans = 0, t;

void upd(int idx, ll x) { for (int i = idx; i <= mxN; i += i & -i) fen[i] += x; }
ll qr(int idx) { ll x = 0; for (int i = idx; i > 0; i -= i & -i) x += fen[i]; return x; }

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    sort(a+1, a+n+1), reverse(a+1, a+n+1);
    for (int i = 1; i <= n; i++) {
        auto &[h, c] = a[i];
        idx = min(idx, h);
        if (idx >= c) upd(idx+1, -1), upd(idx-c+1, 1), idx -= c, c = 0;
        else upd(idx+1, -1), upd(1, 1), c -= idx, idx = 0;
        if (idx == 0) idx = h;
        upd(idx+1, -1), upd(idx-c+1, 1), idx -= c, c = 0;
        if (idx == 0) idx = h;
    }
    for (int i = 1; i < mxN; i++) t = qr(i), ans += t*(t-1)/2;
    cout << ans << '\n';
}

/*
if there are n sails on each hight, the inefficiency will be n*(n-1)/2

we sort the mast from long to short
*/

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