Submission #1230450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230450		vux2code	Sails (IOI07_sails)	C++20	0 / 100	61 ms	7748 KiB

sails

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegTree {
    int n;
    struct Node { ll mn, lazy; };
    vector<Node> st;

    SegTree(int _n): n(_n), st(4*n+4, {0,0}) {}

    void apply(int p, ll v) {
        st[p].mn   += v;
        st[p].lazy += v;
    }

    void push(int p) {
        if (st[p].lazy) {
            apply(p<<1,   st[p].lazy);
            apply(p<<1|1, st[p].lazy);
            st[p].lazy = 0;
        }
    }

    void pull(int p) {
        st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
    }

    // range add v to [L,R]
    void update(int p, int l, int r, int L, int R, ll v) {
        if (L > r || R < l) return;
        if (L <= l && r <= R) {
            apply(p, v);
            return;
        }
        push(p);
        int m = (l + r) >> 1;
        update(p<<1,   l, m, L, R, v);
        update(p<<1|1, m+1, r, L, R, v);
        pull(p);
    }
    void update(int L, int R, ll v) { update(1, 0, n, L, R, v); }

    // point query at idx
    ll query(int p, int l, int r, int idx) {
        if (l == r) return st[p].mn;
        push(p);
        int m = (l + r) >> 1;
        return idx <= m
             ? query(p<<1,   l, m, idx)
             : query(p<<1|1, m+1, r, idx);
    }
    ll query(int idx) { return query(1, 0, n, idx); }

    // find first position >= x in [l..r] where value < val
    int first_below(int p, int l, int r, int x, ll val) {
        if (r < x || st[p].mn >= val) return -1;
        if (l == r) return l;
        push(p);
        int m = (l + r) >> 1;
        int res = first_below(p<<1,   l, m, x, val);
        if (res != -1) return res;
        return first_below(p<<1|1, m+1, r, x, val);
    }
    int first_below(int x, ll val) { return first_below(1, 0, n, x, val); }
};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> h(n), k(n);
    for(int i = 0; i < n; i++) 
        cin >> h[i] >> k[i];

    // process in increasing height order
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b){
        return h[a] < h[b];
    });

    int H = *max_element(h.begin(), h.end());
    SegTree st(H);

    // exactly the same logic as your BIT version:
    //   let val = st.query(last)
    //   find idx1 = first position < val on [0..h[i]]
    //   find idx2 = first position < val+1 on [0..h[i]]
    //   do two range-adds to simulate adding 1 to [idx1..h[i]] but NOT overshooting
    for(int i: ord) {
        int last = h[i] - k[i];
        ll val = st.query(last);          // how many sails already at 'last'
        int idx1 = st.first_below(0, val+1);       // first pos < val+1 => first < (val+1) == ≤ val
        int idx2 = st.first_below(0, val+2);       // first pos < val+2 => first < (val+2) == ≤ val+1

        // now do two range adds:
        // 1) +1 on [idx1 .. h[i]]
        // 2) -1 on [idx2 .. h[i]]
        st.update(idx1,   h[i],   +1);
        st.update(idx2,   h[i],   -1);
    }

    // collect answer
    ll res = 0;
    for(int i = 0; i <= H; i++){
        ll c = st.query(i);
        res += c * (c-1) / 2;
    }
    cout << res << "\n";
    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