Submission #90175

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90175	2018-12-20T17:48:17 Z	popovicirobert	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	811 ms	263168 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(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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	1 ms	376 KB	Output is correct
3	Correct	2 ms	452 KB	Output is correct
4	Correct	18 ms	6132 KB	Output is correct
5	Correct	22 ms	7568 KB	Output is correct
6	Correct	23 ms	7568 KB	Output is correct
7	Correct	22 ms	7956 KB	Output is correct
8	Correct	194 ms	53400 KB	Output is correct
9	Correct	459 ms	91136 KB	Output is correct
10	Correct	452 ms	103796 KB	Output is correct
11	Correct	480 ms	114100 KB	Output is correct
12	Correct	448 ms	119636 KB	Output is correct
13	Correct	456 ms	148528 KB	Output is correct
14	Correct	475 ms	152136 KB	Output is correct
15	Runtime error	811 ms	263168 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
16	Halted	0 ms	0 KB	-