Submission #90181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90181	2018-12-20T18:03:36 Z	popovicirobert	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	389 ms	152728 KB

apple

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

struct Aint {
    Aint *st, *dr;
    int cnt;
    bool lazy;
    Aint() {
        st = dr = NULL;
        cnt = lazy = 0;
    }
};

Aint *root = new Aint;

inline void solve_lazy(Aint *nod, int l, int r) {
    if(nod != NULL && nod -> lazy == 1) {
        if(l < r) {
            if(nod -> st == NULL) {
                nod -> st = new Aint;
            }
            if(nod -> dr == NULL) {
                nod -> dr = new Aint;
            }
            nod -> st -> lazy = nod -> dr -> lazy = 1;
        }
        nod -> cnt = r - l + 1;
        nod -> lazy = 0;
    }
}

inline void refresh(Aint *nod, int l, int r) {
    nod -> cnt = 0;
    int mid = (l + r) / 2;
    if(nod -> st != NULL) {
        solve_lazy(nod -> st, l, mid);
        nod -> cnt += nod -> st -> cnt;
    }
    if(nod -> dr != NULL) {
        solve_lazy(nod -> dr, mid + 1, r);
        nod -> cnt += nod -> dr -> cnt;
    }
}

void update(Aint *nod, int left, int right, int l, int r) {
    solve_lazy(nod, left, right);
    if(nod -> cnt == right - left + 1) {
        return ;
    }
    if(l <= left && right <= r) {
        nod -> lazy = 1;
        solve_lazy(nod, left, right);
    }
    else {
        int mid = (left + right) / 2;
        if(l <= mid) {
            if(nod -> st == NULL) {
                nod -> st = new Aint;
            }
            update(nod -> st, left, mid, l, r);
        }
        if(mid < r) {
            if(nod -> dr == NULL) {
                nod -> dr = new Aint;
            }
            update(nod -> dr, mid + 1, right, l, r);
        }
        refresh(nod, left, right);
    }
}

int query(Aint *nod, int left, int right, int l, int r) {
    if(nod == NULL) {
        return 0;
    }
    solve_lazy(nod, left, right);
    if(l <= left && right <= r) {
        return nod -> cnt;
    }
    else {
        int mid = (left + right) / 2;
        int ans = 0;
        if(l <= mid) {
            ans += query(nod -> st, left, mid, l, r);
        }
        if(mid < r) {
            ans += query(nod -> dr, mid + 1, right, l, r);
        }
        refresh(nod, left, right);
        return ans;
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m;
    int c = 0;
    while(m > 0) {
        m--;
        int d, x, y;
        cin >> d >> x >> y;
        x += c, y += c;
        if(d == 2) {
            update(root, 1, 1e9, x, y);
        }
        else {
            c = query(root, 1, 1e9, x, y);
            cout << c << "\n";
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	408 KB	Output is correct
4	Correct	13 ms	3812 KB	Output is correct
5	Correct	22 ms	4528 KB	Output is correct
6	Correct	15 ms	4528 KB	Output is correct
7	Correct	15 ms	4560 KB	Output is correct
8	Correct	120 ms	32280 KB	Output is correct
9	Correct	235 ms	55648 KB	Output is correct
10	Correct	229 ms	61224 KB	Output is correct
11	Correct	224 ms	65576 KB	Output is correct
12	Correct	257 ms	67368 KB	Output is correct
13	Correct	220 ms	76256 KB	Output is correct
14	Correct	230 ms	76256 KB	Output is correct
15	Correct	378 ms	139268 KB	Output is correct
16	Correct	389 ms	140636 KB	Output is correct
17	Correct	226 ms	140636 KB	Output is correct
18	Correct	231 ms	140636 KB	Output is correct
19	Correct	369 ms	150536 KB	Output is correct
20	Correct	356 ms	152728 KB	Output is correct