Submission #743721

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743721	2023-05-17T19:00:33 Z	PanosPask	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	343 ms	136400 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;
        y += c + 1;
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	3396 KB	Output is correct
5	Correct	14 ms	4188 KB	Output is correct
6	Correct	13 ms	3928 KB	Output is correct
7	Correct	14 ms	4092 KB	Output is correct
8	Correct	100 ms	30040 KB	Output is correct
9	Correct	237 ms	52256 KB	Output is correct
10	Correct	240 ms	57656 KB	Output is correct
11	Correct	227 ms	61940 KB	Output is correct
12	Correct	237 ms	63800 KB	Output is correct
13	Correct	233 ms	74192 KB	Output is correct
14	Correct	225 ms	75028 KB	Output is correct
15	Correct	343 ms	135500 KB	Output is correct
16	Correct	341 ms	136400 KB	Output is correct
17	Incorrect	219 ms	77352 KB	Output isn't correct
18	Halted	0 ms	0 KB	-