답안 #334440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334440 2020-12-09T07:10:11 Z NhoxZuji 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
48 ms 3180 KB
#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) {}
      |     ^~~~
# 결과 실행 시간 메모리 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