Submission #334440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334440	2020-12-09T07:10:11 Z	NhoxZuji	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	48 ms	3180 KB

apple

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define fi first
#define se second
#define fr(x, y, z) for (int x = y; x <= z; ++x)
#define loop(x) while(x--)
#define read(x)  freopen(x".INP","r",stdin);
#define write(x) freopen(x".OUT","w",stdout);
#define NULL nullptr
#define nametask "main"

using namespace std;
typedef long long ll;

int mi(int x, int y){
    return (x > y ? y : x);
}

int ma(int x, int y){
    return (x > y ? x : y);
}

int n;
struct node{
    int s, l, r;
    node *lid, *rid;

    node(int x, int y) : l(x), r(y), s(0), lid(NULL), rid(NULL) {}

    void upd(int x, int y){
        if (s == r - l + 1) return;
        if (x <= l && r <= y) s = r - l + 1; else
        {
            int mid = (l + r) >> 1;
            if (x <= mid){
                if (!lid) lid = new node(l, mid);
                lid->upd(x, y);
            }
            if (y > mid){
                if (!rid) rid = new node(mid + 1, r);
                rid->upd(x, y);
            }
            s = 0;
            s += (lid ? lid->s : 0);
            s += (rid ? rid->s : 0);
        }
    }

    int query(int x, int y){
        if (x > r || l > y) return 0;
        if (x <= l && r <= y) return s;
        if (s == r - l + 1) return mi(r, y) - ma(x, l) + 1;
        int res = 0;
        res += (lid ? lid->query(x, y) : 0);
        res += (rid ? rid->query(x, y) : 0);
        return res;
    }
};

node root(1, (int) 1e9);

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //read(nametask); write(nametask);
    cin >> n;

    int c = 0;
    loop(n){
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1){
            c = root.query(x + c, y + c);
            cout << c << "\n";
        } else root.upd(x + c, y + c);
    }
    return 0;
}

Compilation message

apple.cpp:16: warning: "NULL" redefined
   16 | #define NULL nullptr
      | 
In file included from /usr/include/uchar.h:29,
                 from /usr/include/c++/9/cuchar:53,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:61,
                 from apple.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:392: note: this is the location of the previous definition
  392 | #define NULL __null
      | 
apple.cpp: In constructor 'node::node(int, int)':
apple.cpp:32:15: warning: 'node::r' will be initialized after [-Wreorder]
   32 |     int s, l, r;
      |               ^
apple.cpp:32:9: warning:   'int node::s' [-Wreorder]
   32 |     int s, l, r;
      |         ^
apple.cpp:35:5: warning:   when initialized here [-Wreorder]
   35 |     node(int x, int y) : l(x), r(y), s(0), lid(NULL), rid(NULL) {}
      |     ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	5 ms	492 KB	Output is correct
5	Correct	5 ms	492 KB	Output is correct
6	Correct	5 ms	492 KB	Output is correct
7	Correct	5 ms	492 KB	Output is correct
8	Correct	22 ms	1388 KB	Output is correct
9	Correct	41 ms	2284 KB	Output is correct
10	Correct	43 ms	2412 KB	Output is correct
11	Correct	43 ms	2540 KB	Output is correct
12	Correct	41 ms	2540 KB	Output is correct
13	Correct	48 ms	2668 KB	Output is correct
14	Correct	48 ms	2668 KB	Output is correct
15	Correct	41 ms	3052 KB	Output is correct
16	Correct	45 ms	3052 KB	Output is correct
17	Correct	39 ms	2924 KB	Output is correct
18	Correct	38 ms	2924 KB	Output is correct
19	Correct	45 ms	3180 KB	Output is correct
20	Correct	42 ms	3052 KB	Output is correct