Submission #719312

#TimeUsernameProblemLanguageResultExecution timeMemory
719312Muaath_5Monkey and Apple-trees (IZhO12_apple)C++17
0 / 100
1 ms292 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll N = 1e12+2;

int q;

struct segnode {
    segnode() {}
    //segnode(int s, int idx) : sum(s), s(idx), e(idx) {}
    segnode(segnode* l, segnode* r, ll s, ll e) : segleft(l), segright(r), s(s), e(e) {
        if (l)
            this->sum += l->sum;
        if (r)
            this->sum += r->sum;
    }
    int sum = 0;
    int lazy = 0;
    ll s = 0, e = N;
    segnode* segleft = nullptr, * segright = nullptr;
};

segnode* root;

void pushdown(segnode* node)
{
    if (!node->lazy) return;
    const ll mid = (node->s + node->e) / 2;
    if (!node->segleft && node->s < node->e) {
        node->segleft = new segnode(nullptr, nullptr, node->s, mid);
        node->segleft->lazy = node->lazy;
    }
    if (!node->segright && node->s < node->e) {
        node->segright = new segnode(nullptr, nullptr, mid + 1, node->e);
        node->segright->lazy = node->lazy;
    }
    node->sum = (node->e - node->s + 1) * node->lazy;
    node->lazy = 0;
}

void lazy_update(segnode* node, int l, int r) {
    pushdown(node);
    if (node->e < l || node->s > r) return;
    if (l <= node->s && node->e <= r) {
        node->lazy = 1;
        pushdown(node);
        return;
    }
    const ll mid = (node->s + node->e) / 2;
    int sum = 0;

    if (!node->segleft && node->s < node->e)
        node->segleft = new segnode(nullptr, nullptr, node->s, mid);
    if (!node->segright && node->s < node->e)
        node->segright = new segnode(nullptr, nullptr, mid+1, node->e);

    if (node->segleft) {
        lazy_update(node->segleft, l, r);
        sum += node->segleft->sum;
    }
    if (node->segright) {
        lazy_update(node->segright, l, r);
        sum += node->segright->sum;
    }
    node->sum = sum;
}

int query(segnode* node, int l, int r) {
    pushdown(node);
    if (node->e < l || node->s > r) return 0;
    if (l <= node->s && node->e <= r) return node->sum;
    int sum = 0;
    if (node->segleft)
        sum += query(node->segleft, l, r);
    if (node->segright)
        sum += query(node->segright, l, r);
    return sum;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> q;
    root = new segnode(nullptr, nullptr, 0, N);
    ll c = 0;
    while (q--) {
        int cmd, x, y;
        cin >> cmd >> x >> y;
        if (cmd == 1) {
            c = query(root, x+c, y+c);
            cout << c << '\n';
        }
        else if (cmd == 2) {
            lazy_update(root, x+c, y+c);
        }
    }
}

Compilation message (stderr)

apple.cpp: In constructor 'segnode::segnode(segnode*, segnode*, long long int, long long int)':
apple.cpp:21:35: warning: 'segnode::segright' will be initialized after [-Wreorder]
   21 |     segnode* segleft = nullptr, * segright = nullptr;
      |                                   ^~~~~~~~
apple.cpp:20:8: warning:   'long long int segnode::s' [-Wreorder]
   20 |     ll s = 0, e = N;
      |        ^
apple.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     segnode(segnode* l, segnode* r, ll s, ll e) : segleft(l), segright(r), s(s), e(e) {
      |     ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...