Submission #925053

#	Time	Username	Problem	Language	Result	Execution time	Memory
925053		sheldon	Sails (IOI07_sails)	C++14	100 / 100	151 ms	8536 KiB

sails

#include <bits/stdc++.h>

using namespace std;



struct Node {
    long long sum = 0, mx = 0, lazy = 0;

    void push (Node &left, Node &right, int sz) {
        left.sum += lazy * sz / 2;
        right.sum += lazy * sz / 2;
        left.mx += lazy;
        right.mx += lazy;
        left.lazy += lazy;
        right.lazy += lazy;
        lazy = 0;
    }

    void get (Node &left, Node &right) {
        sum = left.sum + right.sum;
        mx = max(left.mx, right.mx);
    }

};

vector<Node> tree;

long long query (int node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) {
        return 0;
    }

    if (ql <= l && r <= qr) {
        // cout << l << ' ' << r << ' ' << tree[node].sum << '\n';
        return tree[node].sum;
    }

    tree[node].push(tree[node * 2], tree[node * 2 + 1], r - l + 1);

    int mid = (l + r) / 2;
    return query (node * 2, l, mid, ql, qr) + query (node * 2 + 1, mid + 1, r, ql, qr);
}

int get_num (int node, int l, int r, int idx) {

    if (l == r) {
        return tree[node].sum;
    }

    tree[node].push(tree[node * 2], tree[node * 2 + 1], r - l + 1);

    int mid = (l + r) / 2;
    
    if (idx <= mid) {
        return get_num (node * 2, l, mid, idx);
    } else {
        return get_num (node * 2 + 1, mid + 1, r, idx);
    }
}

int get_last_element (int node, int l, int r, int x) {

    if (l == r) {
        return (tree[node].sum != x ? -1 : l);
    }

    int mid = (l + r) / 2;
    tree[node].push(tree[node * 2], tree[node * 2 + 1], r - l + 1);
    if (tree[node * 2].mx < x) {
        return get_last_element (node * 2 + 1, mid + 1, r, x);
    } else if (tree[node * 2].mx == x) {
        // maybe no exist
        return max (mid, get_last_element (node * 2 + 1, mid + 1, r, x));
    } else {
        return get_last_element (node * 2, l, mid, x);
    }
}

int get_first_element (int node, int l, int r, int x) {

    if (l == r) {
        return l;
    }

    tree[node].push(tree[node * 2], tree[node * 2 + 1], r - l + 1);

    int mid = (l + r) / 2;

    if (tree[node * 2].mx < x) {
        return get_first_element (node * 2 + 1, mid + 1, r, x);
    } else {
        return get_first_element(node * 2, l, mid, x);
    }
}

void update (int node, int l, int r, int ql, int qr, int x) {
    if (ql > r || qr < l) {
        return;
    }

    if (ql <= l && r <= qr) {
        tree[node].sum += x * (r - l + 1);
        tree[node].mx += x;
        tree[node].lazy += x;
        return;
    }

    tree[node].push(tree[node * 2], tree[node * 2 + 1], r - l + 1);

    int mid = (l + r) / 2;

    update (node * 2, l, mid, ql, qr, x);
    update (node * 2 + 1, mid + 1, r, ql, qr, x);

    tree[node].get (tree[node * 2], tree[node * 2 + 1]);
}



void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    int base = 100005;

    while (__builtin_popcount(base) != 1) {
        ++base;
    }
    tree.resize (base * 2);
    sort(a.begin(), a.end());
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        int people = a[i].second, height = a[i].first;
        // cout << height << ' ' << people << '\n';
        int start = base - height;
        int end = start + people - 1;
        // cout << "FOR " << start << ' ' << end << '\n';
        ans += query (1, 0, base - 1, start, end);
        // cout << '\n';
        if (get_num (1, 0, base - 1, end) == 0) {
            int idx = get_last_element(1, 0, base - 1, 0);
            update (1, 0, base - 1, idx - people + 1, idx, 1);
        } else {
            int val = get_num (1, 0, base - 1, end);
            int first_pos = get_first_element (1, 0, base - 1, val);
            int last_pos = get_last_element(1, 0, base - 1, val);
            int need = end - first_pos + 1;
            if (start <= first_pos - 1)
                update (1, 0, base - 1, start, first_pos - 1, 1);
            
            update (1, 0, base - 1, last_pos - need + 1, last_pos, 1);
        }
       
    }
    // cout << get_num (1, 0, base - 1, base - 1);
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

• 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