Submission #1098769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098769		Ali_BBN	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	169 ms	71248 KiB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
#define migmig cin.tie(NULL);ios_base::sync_with_stdio(false)
#define max_heap(T) priority_queue<T>
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define pb push_back
#define fi first
#define sec second
#define endl "\n"
#define pii pair <int, int>
using namespace std;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const ll INF18 = 1e18;
const int MAXN = 7e7 + 1;
const int LOG = 23;
int node[MAXN], n = 1e9 + 1, lzy[MAXN], lft[MAXN], rgt[MAXN], now = 1;
ll get(int s, int e, int l = 0, int r = n, int id = 1){
	if (s <= l && e >= r) return node[id];
	if (s >= r || e <= l) return 0;
	int mid = (l + r) / 2;
    if (lft[id] == 0) lft[id] = ++now;
    if (rgt[id] == 0) rgt[id] = ++now;
    if (lzy[id]){
        lzy[lft[id]] = 1;
        lzy[rgt[id]] = 1;
        node[lft[id]] = mid - l;
        node[rgt[id]] = r - mid;
    }
    lzy[id] = 0;
    return get(s, e, l, mid, lft[id]) + get(s, e, mid, r, rgt[id]);
}
void upd(int s, int e, int l = 0, int r = n, int id = 1){
	if (s <= l && e >= r){
        lzy[id] = 1, node[id] = r - l;
        return;
    }
	if (s >= r || e <= l) return;
	int mid = (l + r) / 2;
    if (lft[id] == 0) lft[id] = ++now;
    if (rgt[id] == 0) rgt[id] = ++now;
    if (lzy[id]){
        lzy[lft[id]] = 1;
        lzy[rgt[id]] = 1;
        node[lft[id]] = mid - l;
        node[rgt[id]] = r - mid;
    }
    upd(s, e, l, mid, lft[id]);
    upd(s, e, mid, r, rgt[id]);
    node[id] = node[lft[id]] + node[rgt[id]];
}
void solve(){
	int m;
	cin >> m;
    int c = 0;
	for (int i = 0; i < m; i++){
		int d, l, r;
        cin >> d >> l >> r;
        l--;
        l += c, r += c;
        if (d == 1){
            c = get(l, r);
            cout << c << endl;
        }
        else upd(l, r);
	}
}
int main(){
	migmig;
	int tc = 1;
	// cin >> tc;
	for (int ti = 0; ti < tc; ti++) solve();
}

• Subtask 1: 100 / 100