Submission #421409

#	Time	Username	Problem	Language	Result	Execution time	Memory
421409		tengiz05	Snowball (JOI21_ho_t2)	C++17	0 / 100	165 ms	235132 KiB

Main

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