Submission #1361052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361052		qwertzztrewq	Sails (IOI07_sails)	C++20	70 / 100	1095 ms	1988 KiB

sails

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define fst first
#define snd second

template <typename t>
using vv = vector<t>;
template <typename a, typename b>
using pp = pair<a, b>;

typedef long long ll;
typedef double db;

const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vv<pp<int, int>> idk(n);
    for (auto& p : idk) cin >> p.fst >> p.snd;
    sort(all(idk));
    vv<ll> cat(idk.back().fst, 0);
    for (auto [h, k] : idk) {
        int p = h - k, p2 = p;
        while (p2 && cat[p2 - 1] == cat[p2]) p2--;
        while (p < h - 1 && cat[p + 1] == cat[p]) p++;
        int cnt = k;
        for (int i = p + 1; i < h; i++) cat[i]++, cnt--;
        for (int i = p2; i < p2 + cnt; i++) cat[i]++;
    }
    ll ans = 0;
    for (ll x : cat) ans += 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: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10