Submission #743724

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743724	2023-05-17T19:04:14 Z	PanosPask	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	337 ms	139388 KB

apple

#include <bits/stdc++.h>

using namespace std;

struct SparseTree {
    struct Node {
        Node *l;
        Node* r;
        int val;
        int lazy = 0;

        Node(int v) : val(v), l(nullptr), r(nullptr) {};
        Node(Node* a, Node* b) : val(a->val + b->val), l(a), r(b) {};
    };

    int size;
    Node *null = new Node(0), *root;

    void init(int n) {
        size = n;
        null->l = null;
        null->r = null;
        null->val = 0;
        root = null;
    }

    void prop(Node* x, int lx, int rx) {
        if (x->lazy == 0)
            return;

        int mid = (lx + rx) / 2;
        if (x->l == null)
            x->l = new Node(null, null);
        if (x->r == null)
            x->r = new Node(null, null);

        x->l->lazy = x->r->lazy = x->lazy;
        x->l->val = (mid - lx) * x->l->lazy;
        x->r->val = (rx - mid) * x->r->lazy;

        x->lazy = 0;
    }

    Node* set(int l, int r, int v, Node* x, int lx, int rx)
    {
        if (x == null)
            x = new Node(null, null);

        if (l >= rx || lx >= r)
            return x;
        else if (l <= lx && rx <= r) {
            x->lazy = v;
            x->val = (rx - lx) * v;
            return x;
        }

        prop(x, lx, rx);

        int mid = (lx + rx) / 2;
        x->l = set(l, r, v, x->l, lx, mid);
        x->r = set(l, r, v, x->r, mid, rx);
        x->val = x->l->val + x->r->val;

        return x;
    }
    void set(int l, int r, int v) {
        root = set(l, r, v, root, 0, size);
    }

    int get(int l, int r, Node* x, int lx, int rx) {
        if (l >= rx || lx >= r || x == null)
            return 0;
        else if (l <= lx && rx <= r)
            return x->val;

        prop(x, lx, rx);

        int mid = (lx + rx) / 2;
        int s1 = get(l, r, x->l, lx, mid);
        int s2 = get(l, r, x->r, mid, rx);

        return s1 + s2;
    }
    int get(int l, int r) {
        return get(l, r, root, 0, size);
    }
};

int n = 1e9, q;
SparseTree Tree;
int c = 0;

int main(void)
{
    scanf("%d", &q);
    Tree.init(n);

    while (q--) {
        int d, x, y;
        scanf("%d %d %d", &d, &x, &y);
        x += c - 1;
        y += c;
        if (d == 1) {
            c = Tree.get(x, y);
            printf("%d\n", c);
        }
        else
            Tree.set(x, y, 1);
    }

    return 0;
}

Compilation message

apple.cpp: In constructor 'SparseTree::Node::Node(int)':
apple.cpp:9:13: warning: 'SparseTree::Node::val' will be initialized after [-Wreorder]
    9 |         int val;
      |             ^~~
apple.cpp:7:15: warning:   'SparseTree::Node* SparseTree::Node::l' [-Wreorder]
    7 |         Node *l;
      |               ^
apple.cpp:12:9: warning:   when initialized here [-Wreorder]
   12 |         Node(int v) : val(v), l(nullptr), r(nullptr) {};
      |         ^~~~
apple.cpp: In constructor 'SparseTree::Node::Node(SparseTree::Node*, SparseTree::Node*)':
apple.cpp:9:13: warning: 'SparseTree::Node::val' will be initialized after [-Wreorder]
    9 |         int val;
      |             ^~~
apple.cpp:7:15: warning:   'SparseTree::Node* SparseTree::Node::l' [-Wreorder]
    7 |         Node *l;
      |               ^
apple.cpp:13:9: warning:   when initialized here [-Wreorder]
   13 |         Node(Node* a, Node* b) : val(a->val + b->val), l(a), r(b) {};
      |         ^~~~
apple.cpp: In function 'int main()':
apple.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
apple.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d %d %d", &d, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	11 ms	3268 KB	Output is correct
5	Correct	16 ms	3900 KB	Output is correct
6	Correct	13 ms	3772 KB	Output is correct
7	Correct	13 ms	3988 KB	Output is correct
8	Correct	101 ms	29200 KB	Output is correct
9	Correct	204 ms	50636 KB	Output is correct
10	Correct	208 ms	55876 KB	Output is correct
11	Correct	223 ms	60136 KB	Output is correct
12	Correct	235 ms	61968 KB	Output is correct
13	Correct	213 ms	72268 KB	Output is correct
14	Correct	223 ms	72860 KB	Output is correct
15	Correct	331 ms	133268 KB	Output is correct
16	Correct	332 ms	134356 KB	Output is correct
17	Correct	220 ms	75404 KB	Output is correct
18	Correct	210 ms	77424 KB	Output is correct
19	Correct	337 ms	139384 KB	Output is correct
20	Correct	332 ms	139388 KB	Output is correct