제출 #421372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421372		tengiz05	Snowball (JOI21_ho_t2)	C++17	0 / 100	2639 ms	750864 KiB

Main

#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
• Subtask 2: 0 / 67