Submission #335316

#	Time	Username	Problem	Language	Result	Execution time	Memory
335316		jovan_b	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	50 ms	3052 KiB

apple

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

typedef long long ll;
typedef long double ld;

#define pb push_back

int intersect(int l, int r, int tl, int tr){
    return max(0, min(tr, r)-max(l, tl)+1);
}

struct segment{
    int val;
    bool lazy;
    segment* c[2];
    segment() {c[0] = c[1] = NULL;}
    void upd(int l, int r, int tl, int tr){
        if(val == r-l+1) return;
        if(tl <= l && r <= tr){
            val = r-l+1;
            return;
        }
        int mid = (ll(l)+r)/2;
        if(intersect(l, mid, tl, tr)){
            if(!c[0]) c[0] = new segment();
            c[0]->upd(l, mid, tl, tr);
        }
        if(intersect(mid+1, r, tl, tr)){
            if(!c[1]) c[1] = new segment();
            c[1]->upd(mid+1, r, tl, tr);
        }
        val = 0;
        if(c[0]) val += c[0]->val;
        if(c[1]) val += c[1]->val;
    }
    int query(int l, int r, int tl, int tr){
        if(val == r-l+1) return intersect(l, r, tl, tr);
        if(tl <= l && r <= tr) return val;
        int mid = (ll(l)+r)/2;
        int res = 0;
        if(intersect(l, mid, tl, tr) && c[0]) res += c[0]->query(l, mid, tl, tr);
        if(intersect(mid+1, r, tl, tr) && c[1]) res += c[1]->query(mid+1, r, tl, tr);
        return res;
    }
};

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

    segment *ROOT = new segment();
    int m;
    cin >> m;
    const int n = 1000000000;
    int res = 0;
    for(int i=1; i<=m; i++){
        int t, l, r;
        cin >> t >> l >> r;
        l += res;
        r += res;
        if(t == 1){
            res = ROOT->query(1, n, l, r);
            cout << res << "\n";
        }
        else{
            ROOT->upd(1, n, l, r);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100