Submission #339792

#	Time	Username	Problem	Language	Result	Execution time	Memory
339792		Vladikus004	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	522 ms	207812 KiB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

struct node{
    int sum, tl, tr, mod;
    node *l, *r;
    node(){
        sum = 0; tl = tr = mod = -1;
        l = r = nullptr;
    }
    node(int L, int R, int SUM){
        sum = SUM; tl = L; tr = R;
        mod = -1;
        l = r = nullptr;
    }
};

const int SZ = (int)1e9+3;
node *root = new node(0, SZ, 0);

void push(node *v){
    if (v->tl == v->tr) return;
    int tm = (v->tl + v->tr) / 2;
    if (!v->l)
        v->l = new node(v->tl, tm, 0);
    if (!v->r)
        v->r = new node(tm + 1, v->tr, 0);
    if (v->mod != -1){
        v->l->mod = v->mod;
        v->r->mod = v->mod;
        v->l->sum = (v->l->tr - v->l->tl + 1) * (v->mod);
        v->r->sum = (v->r->tr - v->r->tl + 1) * (v->mod);
        v->mod = -1;
    }
}

void up(node *v, int l, int r, int val){
    if (l > r) return;
    if (v->tl == l && v->tr == r) {
        v->sum = val * (v->tr - v->tl + 1);
        v->mod = val;
        return;
    }
    push(v);
    int tm = (v->tr + v->tl) / 2;
    up(v->l, l, min(r, tm), val);
    up(v->r, max(tm + 1, l), r, val);
    v->sum = v->l->sum + v->r->sum;
}

int get_sum(node *v, int l, int r){
    if (l > r) return 0;
    if (v->tl == l && v->tr == r) return v->sum;
    push(v);
    int tm = (v->tr + v->tl) / 2;
    int ans = 0;
    ans += get_sum(v->l, l, min(r, tm));
    ans += get_sum(v->r, max(l, tm + 1), r);
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);
    int m;
    cin >> m;
    int c = 0;
    while (m--){
        int tp,l,r;
        cin >> tp >> l >> r;
        if (tp == 1){
            cout << (c = get_sum(root, l + c, r + c))    << "\n";
//            up(root, l + c, r + c, 0);
        }else{
            up(root, l + c, r + c, 1);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100