oj.uz

Submission #421372

# Submission time Handle Problem Language Result Execution time Memory
421372 2021-06-09T05:56:25 Z tengiz05 Snowball (JOI21_ho_t2) C++17
0 / 100
 2500 ms 750864 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 extra = 5e16;
struct node{
    node *l, *r;
    i64 sum;
    bool lz;
    node(i64 L, i64 R) {
        l = r = nullptr;
        sum = R - L + 1;
        lz = 0;
    }
};
void makechild(node *x, i64 l, i64 r) {
    i64 mid = (l + r) / 2;
    if (x->l == nullptr) {
        x->l = new node(l, mid);
    }
    if (x->r == nullptr) {
        x->r = new node(mid + 1, r);
    }
}
i64 get(i64 l, i64 r, i64 L, i64 R, node *x) {
    if (x == nullptr || L > r || R < l) return 0;
    if (x->lz) return 0;
    if (L >= l && R <= r) {
        return x->sum;
    } else {
        i64 mid = (L + R) / 2;
        makechild(x, L, R);
        return get(l, r, L, mid, x->l) + get(l, r, mid + 1, R, x->r);
    }
}
void update(i64 l, i64 r, i64 L, i64 R, node *x) {
    if (x == nullptr || L > r || R < l) return;
    if (x->lz) return;
    if (L >= l && R <= r) {
        x->sum = 0;
        x->lz = true;
    } else {
        i64 mid = (L + R) / 2;
        makechild(x, L, R);
        update(l, r, L, mid, x->l);
        update(l, r, mid + 1, R, x->r);
        x->sum = x->l->sum + x->r->sum;
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, Q;
    std::cin >> n >> Q;
    std::vector<i64> a(n);
    std::vector<i64> ans(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i] += extra;
    }
    node *root = new node(0, extra * 4);
    sort(a.begin(), a.end());
    while (Q--) {
        i64 x;
        std::cin >> x;
        if (x == 0) {
            continue;
        } else if (x > 0) {
            for (int i = n - 1; i >= 0; i--) {
                ans[i] += get(a[i], a[i] + x - 1, 0, extra * 4, root);
                update(a[i], a[i] + x - 1, 0, extra * 4, root);
                a[i] += x;
            }
        }  else {
            for (int i = 0; i < n; i++) {
                ans[i] += get(a[i] + x, a[i] - 1, 0, extra * 4, root);
                update(a[i] + x, a[i] - 1, 0, extra * 4, root);
                a[i] += x;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10776 KB Output is correct
2 Correct 142 ms 50804 KB Output is correct
3 Correct 1264 ms 393756 KB Output is correct
4 Execution timed out 2639 ms 750864 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10776 KB Output is correct
2 Correct 142 ms 50804 KB Output is correct
3 Correct 1264 ms 393756 KB Output is correct
4 Execution timed out 2639 ms 750864 KB Time limit exceeded
5 Halted 0 ms 0 KB -