Submission #719327

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

const int N = 1e9+10;

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

segnode* root;

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

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++;
        pushdown(node);
        return;
    }
    const int 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);
    int q, cmd, x, y;
    cin >> q;
    root = new segnode();
    int c = 0;
    while (q--) {
        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*, int, int)':
apple.cpp:11:24: warning: 'segnode::segright' will be initialized after [-Wreorder]
   11 |     segnode *segleft, *segright;
      |                        ^~~~~~~~
apple.cpp:10:9: warning:   'int segnode::s' [-Wreorder]
   10 |     int s, e;
      |         ^
apple.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     segnode(segnode* l, segnode* r, int s, int e) : segleft(l), segright(r), s(s), e(e) {
      |     ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...