oj.uz

Submission #1038411

# Submission time Handle Problem Language Result Execution time Memory
1038411 2024-07-29T19:01:37 Z Thunnus Sails (IOI07_sails) C++17
0 / 100
 50 ms 3796 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 2272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 3564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 3792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -