Submission #1038411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038411		Thunnus	Sails (IOI07_sails)	C++17	0 / 100	50 ms	3796 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 bs = [&](int lo, int hi, function<bool(int)> check) -> int {
        int ret = sz(cur_h);
        while(hi >= lo){
            int mid = lo + (hi - lo) / 2;
            if(check(mid)){
                lo = mid + 1;
                ret = mid;
            }
            else
                hi = 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) - 1 - k);
        int l = bs(0, sz(cur_h) - 1, [&](int idx) {return bit.sum(idx) >= last_val;} ) + 1;
        int r = bs(0, sz(cur_h) - 1, [&](int idx) {return bit.sum(idx) > last_val;} );
        //cout << "h: " << h << " k: " << k << " l: " << l << " r: " << r << " size: " << sz(cur_h) << "\n";
        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);
        //cout << "i: " << i << " val: " << val << "\n";
        ans += val * (val + 1) / 2;
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10