Submission #878609

#	Time	Username	Problem	Language	Result	Execution time	Memory
878609		PagodePaiva	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	0 ms	600 KiB

apple

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e9;

struct Node{
    int value;
    int lazy;
    Node *lc, *rc;

    Node(){
        value = 0;
        lazy = 0;
        lc = NULL;
        rc = NULL;
    }

    void newnode(){
        if(lc == NULL) lc = new Node();
        if(rc == NULL) rc = new Node();
    }
};

Node* seg = new Node();

void unlazy(Node *current, int l, int r){
    if(current -> lazy == 0) return;
    current -> value = (r-l+1)*(current -> lazy);

    if(l < r){
        current -> newnode();
        current -> lc -> lazy = current -> lazy;
        current -> rc -> lazy = current -> lazy;    
    }
    current -> lazy = 0;
    return;
}

void update(Node *current, int l, int r, int val, int tl, int tr){
    // cout << tl << ' ' << tr << '\n';
    unlazy(current, tl, tr);
    if(tl > r or tr < l) return;
    if(l <= tl and tr <= r){
        current -> lazy = val;
        // cout << tl << ' ' << tr << '\n';
        // cout << current -> value << ' ' << current -> lazy << '\n';
        unlazy(current, tl, tr);
        // cout << current -> value << ' ' << current -> lazy << '\n';

        return;
    }

    int mid = (tl+tr)/2;
    current -> newnode();
    update(current -> lc, l, r, val, tl, mid);
    update(current -> rc, l, r, val, mid+1, tr);

    current -> value = current -> lc -> value + current -> rc -> value; 
    return;
}

int query(Node *current, int l, int r, int tl, int tr){
    // cout << tl << ' ' << tr << '\n';
    unlazy(current, tl, tr);
    if(tl > r or tr < l) return 0;
    if(l <= tl and tr <= r) {
        // cout << tl << ' ' << tr << '\n';
        // cout << current -> value << ' ' << current -> lazy << '\n';
        return current -> value;
    }
    
    int mid = (tl+tr)/2;
    current -> newnode();
    return query(current -> lc, l, r, tl, mid) + query(current -> rc, l, r, mid+1, tr);
}

int32_t main(){
    int q;
    cin >> q;

    int c = 0;
    while(q--){
        int d, l, r;
        cin >> d >> l >> r;
        l += c;
        r += c;

        if(d == 1){
            int res = query(seg, l, r, 1, N);
            c += res;
            cout << res << '\n';
        }

        else{
            update(seg, l, r, 1, 1, N);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100