Submission #155036

#	Time	Username	Problem	Language	Result	Execution time	Memory
155036		jovan_b	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2 ms	376 KiB

apple

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int c;
const int INF = 1000000000;

struct segment{
    int val;
    int l, r;
    int lazy;
} seg[10000000];

int cnt = 1;

void create(int node, int l, int r){
    seg[node].l = ++cnt;
    seg[node].r = ++cnt;
    int mid = ((ll)l+r)/2;
    if(seg[node].lazy){
        seg[cnt-1].val = mid-l+1;
        seg[cnt-1].lazy = 1;
        seg[cnt].val = r-mid;
        seg[cnt].lazy = 1;
    }
}

void propagate(int node, int l, int r){
    if(!seg[node].lazy) return;
    seg[node].val = r-l+1;
    if(l == r) return;
    if(!seg[node].l) create(node, l, r);
    int mid = (l+r)/2;
    seg[seg[node].l].val = mid-l+1;
    seg[seg[node].r].val = r-mid;
}

void upd(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy = 1;
        seg[node].val = r-l+1;
        propagate(node, l, r);
        return;
    }
    int mid = ((ll)l+r)/2;
    if(!seg[node].l) create(node, l, r);
    upd(seg[node].l, l, mid, tl, tr);
    upd(seg[node].r, mid+1, r, tl, tr);
    seg[node].val = seg[seg[node].l].val + seg[seg[node].r].val;
}

int query(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return 0;
    if(tl <= l && r <= tr) return seg[node].val;
    int mid = ((ll)l+r)/2;
    if(!seg[node].l) return (seg[node].val > 0)*(min(r, tr) - max(l, tl));
    return query(seg[node].l, l, mid, tl, tr) + query(seg[node].r, mid+1, r, tl, tr);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int m;
    cin >> m;
    while(m--){
        int a, l, r;
        cin >> a >> l >> r;
        l += c;
        r += c;
        if(a == 2){
            upd(1, 1, INF, l, r);
        }
        if(a == 1){
            c = query(1, 1, INF, l, r);
            cout << c << "\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 100