Submission #1361122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361122		lacito	Sails (IOI07_sails)	C++20	70 / 100	1095 ms	1504 KiB

sails

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
    int n, high=0;
    cin >> n;
    vector<pair<int, int>> mast(n);
    vector<int> cnt(100001);
    cnt[0] = 100001;
    for (int i = 0; i < n; i++) {
        cin >> mast[i].first >> mast[i].second;
        high = max(high, mast[i].first);
    }
    sort(mast.begin(), mast.end());
    for (int i = 0; i < n; i++) {
        int h = mast[i].first, k = mast[i].second;
		// cerr << h << " " << k << endl;
        for (int j = h; j > h - k; j--) {
            cnt[j]++;
        }
        // for (int i = 0; i <= 10; i++) cerr << cnt[i] << " "; cerr << endl;
        if (cnt[h - k] < cnt[h - k + 1]) {
            int j = h - k, l = h - k + 1;
            while (cnt[l] == cnt[h - k + 1])l++;
            // for (int i = 0; i <= 10; i++) cerr << cnt[i] << " "; cerr << endl;
            while (cnt[j] == cnt[h - k]) {
                // cerr << j << " " << cnt[j] << endl;
                j--;
            }
            for (int m = j+1; m - j <= l - (h - k + 1); m++) cnt[m]++;
            for (int m = h - k + 1; m < l; m++)cnt[m]--;
        }
        // for (int i = 0; i <= 10; i++) cerr << cnt[i] << " "; cerr << endl;
    }
    ll ans = 0;
    for (int i = 1; i <= high; i++) {
        ans += ll(cnt[i]) * ll(cnt[i] - 1) / 2;
    }
    cout << ans;
}

• 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: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10