Submission #890535

#	Time	Username	Problem	Language	Result	Execution time	Memory
890535		sheldon	Sails (IOI07_sails)	C++14	5 / 100	106 ms	7308 KiB

sails

#include <bits/stdc++.h>

using namespace std;


struct Node {
    long long sum = 0, lazy = 0, sz = 1;
    void push (Node &left, Node &right) {
        left.sum += lazy * sz / 2;
        right.sum += lazy * sz / 2;
        left.lazy += lazy;
        right.lazy += lazy;
        lazy = 0;
    }
    void merge (Node &left, Node &right) {
        sum = left.sum + right.sum;
        sz = left.sz + right.sz;
    }
};

vector<Node> tree;

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 += tree[node].sz * x;
        tree[node].lazy += x;
        return;
    }
    int mid = (l + r) / 2;
    tree[node].push(tree[node * 2], tree[node * 2 + 1]);
    update (node * 2 , l, mid, ql, qr, x);
    update (node * 2 + 1, mid + 1, r, ql, qr, x);
    tree[node].merge(tree[node * 2], tree[node * 2 + 1]);
}

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) {
        return tree[node].sum;
    }
    int mid = (l + r) / 2;
    tree[node].push(tree[node * 2], tree[node * 2 + 1]);
    return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
}
void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> tower(n);
    for (int i = 0; i < n; ++i) {
        cin >> tower[i].first >> tower[i].second;
    }
    sort(tower.rbegin(), tower.rend());
    int base = tower[0].first, idx = tower[0].first - 1;
    while (__builtin_popcount(base) != 1) {
        ++base;
    }
    tree.resize(base * 2);
    for (int i = base; i < base * 2; ++i) {
        tree[i].sz = 1;
    }
    for (int i = base - 1; i >= 1; --i) {
        tree[i].sz = tree[i * 2].sz + tree[i * 2 + 1].sz;
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        if (idx >= tower[i].first) {
            idx = tower[i].first - 1;
        }
        // cout << tower[i].second << ' ' << idx << ' '  << i << '\n';
        if (tower[i].second - 1 <= idx) {
            update (1, 0, base - 1, idx - (tower[i].second - 1), idx, 1);
            idx = idx - (tower[i].second - 1) - 1;
            if (idx == -1 && i != n - 1)  {
                idx = tower[i + 1].first - 1;
            }
            // edge case idx == -1
        } else {
            update (1, 0, base - 1, 0, idx, 1);
            tower[i].second -= (idx + 1);
            idx = tower[i].first - 1;
            update (1, 0, base - 1, idx - (tower[i].second - 1), idx, 1);
            idx = idx - (tower[i].second - 1) - 1;
        }
    }
    for (int i = 0; i < base; ++i) {
        ans += query(1, 0, base - 1, i, i) * ((query(1, 0, base - 1, i, i) - 1)) / 2;
    }
    cout << ans;
}

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

• Subtask 1: 5 / 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