oj.uz

Submission #421411

# Submission time Handle Problem Language Result Execution time Memory
421411 2021-06-09T06:52:41 Z tengiz05 Snowball (JOI21_ho_t2) C++17
0 / 100
 432 ms 704788 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 extra = 2e16, E = 4e16, N = 3e7;
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;
        sum = 0;
        lz = 0;
    }
} 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);
        }
        assert(timer < N);
        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.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 704688 KB Output is correct
2 Incorrect 432 ms 704788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 704688 KB Output is correct
2 Incorrect 432 ms 704788 KB Output isn't correct
3 Halted 0 ms 0 KB -