Submission #449815

#	Time	Username	Problem	Language	Result	Execution time	Memory
449815		prvocislo	Sails (IOI07_sails)	C++17	100 / 100	72 ms	4636 KiB

sails

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5;
int d[maxn], H = 0; // rozdiel oproti predoslemu, posledny aktivny stlpec
set<int> b;
void add(int l, int r) // chceme pridat l a r vratane
{
    if (r < l) return;
    d[l]++, d[r + 1]--;
    if (d[l] == 0) b.erase(l);
    if (d[r + 1] < 0) b.insert(r + 1);
}
struct mast { int h, k; } ship[maxn];
bool cmp(const mast& a, const mast& b) { return a.h < b.h; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> ship[i].h >> ship[i].k;
    sort(ship, ship + n, cmp);
    b.insert(1);
    //cout << "\n";
    for (int i = 0; i < n; i++)
    {
        if (H != ship[i].h)
        {
            if (H && d[H + 1] == 0) b.erase(H + 1);
            H = ship[i].h;
            b.insert(H + 1);
        }
        int l = H - ship[i].k + 1;
        int l1 = *b.lower_bound(l), r1 = H;
        int len = ship[i].k - max(0, r1 - l1 + 1); 
        int l2 = *prev(b.upper_bound(l)), r2 = l2 + len - 1;
        add(l1, r1);
        add(l2, r2);
        /*for (int i = 1, val = d[1]; i <= H; val += d[++i])
            cout << val << " ";
        cout << "\n";*/
    }
    ll ans = 0;
    for (int i = 1, val = d[1]; i <= H; val += d[++i])
    {
        ans += val * 1ll * (val - 1) / 2ll;
    }
    cout << ans << "\n";
    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