제출 #1368983

#제출 시각아이디문제언어결과실행 시간메모리
1368983hanoon원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
318 ms265848 KiB
#include <bits/stdc++.h>

#define ll long long
#define int  ll
#define ld long double
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvv vector<vvi>
#define vpi vector<pair<int,int>>
#define sz(v) (int)v.size()
#define pb push_back
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int mod = 998244353, N = 1e3+1;
const ll inf = 1e18;
string di[] = {"L", "R", "D", "U", "UR", "UL", "DR", "DL"};
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};

struct Node {
    int l, r;
    int sum = 0;
    int lazy = 0;

    Node *left = nullptr, *right = nullptr;

    Node(int lb, int rb) {
        l = lb;
        r = rb;
    }

    // create children only when needed
    void extend() {
        if (!left && l + 1 < r) {
            int mid = (l + r) >> 1;

            left = new Node(l, mid);
            right = new Node(mid, r);
        }
    }

    // push lazy to children
    void push() {
        if (lazy == 0)
            return;

        extend();

        // leaf node
        if (!left)
            return;

        int mid = (l + r) >> 1;

        left->sum = (mid - l) ;
        right->sum = (r - mid) ;

        left->lazy = 1;
        right->lazy = 1;

        lazy = 0;
    }

    // add val to range [lq, rq)
    void update(int lq, int rq) {

        // no overlap
        if (rq <= l || r <= lq)
            return;

        // full overlap
        if (lq <= l && r <= rq) {
            sum = (r - l);
            lazy = 1;
            return;
        }

        push();
        extend();

        left->update(lq, rq);
        right->update(lq, rq);

        sum = left->sum + right->sum;
    }

    // query sum on range [lq, rq)
    int query(int lq, int rq) {

        // no overlap
        if (rq <= l || r <= lq)
            return 0;

        // full overlap
        if (lq <= l && r <= rq)
            return sum;

        push();
        extend();

        return left->query(lq, rq) +
               right->query(lq, rq);
    }
};
void hanoon_btkrhko() {
    Node seg(0,1e9+2);
    int m,c=0; cin>>m;
    while(m--){
        int d,x,y;
        cin>>d>>x>>y;
        x+=c,y+=c;

        if(d==1){
            c=seg.query(x,y+1);
            cout<<c<<'\n';
        }
        else{
            seg.update(x,y+1);
        }
    }

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int tc = 1;
//    cin >> tc;
    for (int i = 1; i <= tc; ++i) {
//        cout<<"Case #"<<i<<": ";
        hanoon_btkrhko();
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…