제출 #1309920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309920		buzdi	Sails (IOI07_sails)	C++17	100 / 100	71 ms	1540 KiB

sails

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int NMAX = 1e5 + 10;

ll answer;
int n;
pair<int, int> a[NMAX + 1];

struct AIB {
    int n;
    int aib[NMAX + 1];

    void init(int n) {
        this->n = n;
        fill(aib + 1, aib + n + 1, 0);
    }

    void update(int pos, int value) {
        for(int i = pos; i <= n; i += i & (-i)) {
            aib[i] += value;
        }
    }

    void update(int l, int r, int value) {
        update(l, value);
        update(r + 1, -value);
    }

    int query(int pos) {
        int answer = 0;
        for(int i = pos; i >= 1; i -= i & (-i)) {
            answer += aib[i];
        }
        return answer;
    }
}aib;

int last_greater(int ending, int value) {
    int left = 1, right = ending, answer = 0;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(aib.query(mid) >= value) {
            answer = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }
//    cout << '\n';

    int max_h = 0;
    for(int i = 1; i <= n; i++) {
        max_h = max(max_h, a[i].first);
    }
    aib.init(max_h);

    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        auto [h, k] = a[i];

//        for(int j = 1; j <= max_h; j++) {
//            cout << aib.query(j) << ' ';
//        }
//        cout << '\n';
//        cout << h << ' ' << k << '\n';

        int l = h - k + 1;
        int last = aib.query(l);
        int last_pos_last = last_greater(h, last);
        int first_pos_last = last_greater(h, last + 1) + 1;
        int adding_right = h - last_pos_last;
        int adding_left = k - adding_right;

//        cout << last_pos_last + 1 << ' ' << h << '\n';
//        cout << first_pos_last << ' ' << first_pos_last + adding_left - 1 << '\n';
        aib.update(last_pos_last + 1, h, 1);
        aib.update(first_pos_last, first_pos_last + adding_left - 1, 1);
    }

    for(int i = 1; i <= max_h; i++) {
        int x = aib.query(i);
//        cout << x << ' ';
        answer += (ll) x * (x - 1) / 2;
    }
    cout << answer << '\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