Submission #90181

#	Time	Username	Problem	Language	Result	Execution time	Memory
90181		popovicirobert	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	389 ms	152728 KiB

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 / 100