Submission #484786

#	Time	Username	Problem	Language	Result	Execution time	Memory
484786		Alexandruabcde	Sails (IOI07_sails)	C++14	100 / 100	90 ms	3000 KiB

sails

#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 1e5 + 5;
typedef pair <int, int> PII;
typedef long long LL;

int N;

PII a[NMAX];
LL aib[NMAX];

void Update (int pos, int val) {
    for (int i = pos; i <= a[N].first; i += ub(i))
        aib[i] += val;
}

void UpdateInterval (int a, int b, int val) {
    Update(a, val);
    Update(b+1, -val);
}

LL Query (int pos) {
    LL S = 0;
    for (int i = pos; i > 0; i -= ub(i))
        S += aib[i];

    return S;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> a[i].first >> a[i].second;

    sort(a+1, a+N+1);
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        int value = Query(a[i].first - a[i].second + 1);
        int ans_st = a[i].first - a[i].second + 1;
        int ans_dr = a[i].first - a[i].second + 1;

        int st = 1, dr = a[i].first - a[i].second + 1;

        while (st <= dr) {
            int mij = (st + dr) / 2;
            int x = Query(mij);

            if (x == value) {
                ans_st = mij;
                dr = mij - 1;
            }
            else st = mij + 1;
        }

        st = a[i].first - a[i].second + 1;
        dr = a[i].first;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            int x = Query(mij);

            if (x == value) {
                ans_dr = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }

        if (ans_st == a[i].first - a[i].second + 1) {
            UpdateInterval(ans_st, a[i].first, 1);
            continue;
        }

        if (ans_dr < a[i].first)
            UpdateInterval(ans_dr+1, a[i].first, 1);

        UpdateInterval(ans_st, ans_st - (a[i].first - ans_dr) + a[i].second - 1, 1);
    }
}

void Write () {
    LL ans = 0;
    for (int i = 1; i <= a[N].first; ++ i ) {
        LL x = Query(i) - 1;

        ans += x * (x+1) / 2;
    }

    cout << ans << '\n';
}

int main () {
    Read();
    Solve();
    Write();

    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