Submission #421400

#	Time	Username	Problem	Language	Result	Execution time	Memory
421400		tengiz05	Snowball (JOI21_ho_t2)	C++17	0 / 100	2643 ms	977144 KiB

Main

#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 extra = 2e16, E = 4e16;
struct node{
    node *l, *r;
    i64 sum;
    bool lz;
    node(i64 L, i64 R) {
        l = r = nullptr;
        sum = R - L + 1;
        lz = 0;
    }
};
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) {
        i64 ans = x->sum;
        x->sum = 0;
        x->lz = true;
        return ans;
    } else {
        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 ans = get(l, r, L, mid, x->l) + get(l, r, mid + 1, R, x->r);
        x->sum = x->l->sum + x->r->sum;
        return ans;
    }
}
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, E);
    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, E, root);
                a[i] += x;
            }
        }  else {
            for (int i = 0; i < n; i++) {
                ans[i] += get(a[i] + x, a[i] - 1, 0, E, root);
                a[i] += x;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 67