Submission #1219812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219812		vanea	Sails (IOI07_sails)	C++20	100 / 100	835 ms	7280 KiB

sails

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

const int mxN = 4e5+10;

ll st[mxN], st1[mxN], lazy[mxN];

void push(int node, int l, int r) {
    if(l == r) return ;
    int left = node*2, right = node*2+1, mid = (l+r)/2;
    lazy[left] += lazy[node]; lazy[right] += lazy[node];
    st[left] += lazy[node] * (mid - l + 1);
    st[right] += lazy[node] * (r - mid);
    st1[left] += lazy[node]; st1[right] += lazy[node];
    lazy[node] = 0;
}

ll qry(int node, int l, int r, int l1, int r1) {
    push(node, l, r);
    if(l1 <= l && r <= r1) return st[node];
    if(l1 > r || r1 < l) return 0LL;
    int mid = (l+r)/2;
    return qry(node*2, l, mid, l1, r1) + qry(node*2+1, mid+1, r, l1, r1);
    st[node] = st[node*2] + st[node*2+1];
    st1[node] = max(st1[node*2], st1[node*2+1]);
}

void upd(int node, int l, int r, int l1, int r1) {
    push(node, l, r);
    if(l1 <= l && r <= r1) {
        st[node] += (r-l+1);
        lazy[node]++;
        return ;
    }
    if(l > r1 || r < l1) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, l1, r1);
    upd(node*2+1, mid+1, r, l1, r1);
    st[node] = st[node*2] + st[node*2+1];
    st1[node] = max(st1[node*2], st1[node*2+1]);
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, H = 0;
    cin >> n;
    vector<array<int, 2>> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1];
        H = max(H, v[i][0]);
    }

    const auto first_val = [&](int val, int l, int r) {
        ++r;
        while(l < r) {
            int mid = l + (r - l) / 2;
            ll now = qry(1, 1, H, mid, mid);
            if(now >= val) l = mid+1;
            else r = mid;
        }
        return l;
    };
    ll ans = 0;
    sort(v.begin(), v.end());
    for(auto [h, k] : v) {
        ll now = qry(1, 1, H, h-k+1, h);
        ll last = qry(1, 1, H, h-k+1, h-k+1);
        ans += now;
        int f = first_val(last+1, 1, h-k+1);
        int s = first_val(last, h-k+1, h);
        upd(1, 1, H, s, h);
        upd(1, 1, H, f, f + k - (h - s + 1) - 1);
    }
    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