oj.uz

Submission #890535

# Submission time Handle Problem Language Result Execution time Memory
890535 2023-12-21T12:14:15 Z sheldon Sails (IOI07_sails) C++14
5 / 100
 106 ms 7308 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

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 1 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 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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