Submission #1038443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038443		Thunnus	Sails (IOI07_sails)	C++17	100 / 100	71 ms	5072 KiB

sails

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct BIT{
    vi bit;
    BIT(int n) : bit(n + 2) {}

    void add(int idx, int val){
        for(++idx; idx < sz(bit); idx += idx & -idx)
            bit[idx] += val;
    }

    int sum(int idx){
        int ret = 0;
        for(++idx; idx; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, h, k, ans = 0, maxh = 0;
    cin >> n;
    vector<pii> mast(n);
    vi cur_h;
    for(int i = 0; i < n; i++){
        cin >> mast[i].fi >> mast[i].se;
        maxh = max(maxh, mast[i].fi);
    }
    sort(mast.begin(), mast.end());
    BIT bit(maxh + 1);

    auto find_smallest_index = [&](int lo, int hi, int val) -> int {
        int ret = hi + 1;
        while(hi >= lo){
            int mid = lo + (hi - lo) / 2, cur = bit.sum(mid);
            if(cur == val){
                ret = mid;
                hi = mid - 1;
            }
            else if(cur < val)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return ret;
    };

    auto find_greatest_index = [&](int lo, int hi, int val) -> int {
        int ret = hi + 1;
        while(hi >= lo){
            int mid = lo + (hi - lo) / 2, cur = bit.sum(mid);
            if(cur == val){
                ret = mid;
                lo = mid + 1;
            }
            else if(cur < val)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return ret;
    };

    auto range_add = [&](int l, int r, int val) -> void {
        bit.add(l, val);
        bit.add(r + 1, -val);
    };

    for(int i = 0; i < n; i++){
        h = mast[i].fi, k = mast[i].se;
        while(h > sz(cur_h))
            cur_h.emplace_back(0);
        int last_val = bit.sum(sz(cur_h) - k);
        int l = find_smallest_index(0, sz(cur_h) - 1, last_val);
        int r = find_greatest_index(0, sz(cur_h) - 1, last_val);
        if(r + 1 < sz(cur_h)){
            range_add(r + 1, sz(cur_h) - 1, 1);
            int ln = (sz(cur_h) - 1) - (r + 1) + 1, rem = k - ln;
            range_add(l, l + rem - 1, 1);
        }
        else{
            range_add(l, l + k - 1, 1);
        }
    }

    for(int i = 0; i < maxh; i++){
        int val = bit.sum(i);
        ans += val * (val - 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: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10