제출 #1219079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219079		xuhankai	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	289 ms	205680 KiB

apple

#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using orderedMultiset = tree<T ,null_type,std::less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int,int,int> tiii;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i) 
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
ll MOD = 998244353;
 

/*

*/

template<class T> struct node {
    T val;
    T lazy;
    bool lazyFlag;
    T def;
    node* c[2];
    int L, R;

    node(T _def = 0, int l = 0, int r = (1<<30)-1) 
        : val(_def), lazy(_def), lazyFlag(false), def(_def), L(l), R(r) {
        c[0] = c[1] = nullptr;
    }
  
    void apply(T v) { // Apply a range assignment
        val = v * (R-L+1);
        lazy = v;
        lazyFlag = true;
    }
  
    void pushDown() { // Push lazy to children
        if (lazyFlag && L != R) { // If it's not leaf
            int M = (L + R) / 2;
            if (!c[0]) c[0] = new node(def, L, M);
            if (!c[1]) c[1] = new node(def, M + 1, R);
            c[0]->apply(lazy);
            c[1]->apply(lazy);
        }
        lazy = def;
        lazyFlag = false;
    }
  
    T comb(T a, T b) { // Combine two segments
        return a+b;
    }
  
    void range_upd(int ql, int qr, T v) { // range assignment
        if (qr < L || ql > R) return;
        if (ql <= L && R <= qr) { // fully covered
            apply(v);
            return;
        }
        pushDown();
        int M = (L + R) / 2;
        if (!c[0]) c[0] = new node(def, L, M);
        if (!c[1]) c[1] = new node(def, M + 1, R);
        c[0]->range_upd(ql, qr, v);
        c[1]->range_upd(ql, qr, v);
        val = comb(c[0]->val, c[1]->val);
    }
  
    T range_query(int ql, int qr) { 
        if (qr < L || ql > R) return def;
        if (ql <= L && R <= qr) return val;
        pushDown();
        T res = def;
        if (c[0]) res = comb(res, c[0]->range_query(ql, qr)); 
        if (c[1]) res = comb(res, c[1]->range_query(ql, qr)); 
        return res;
    }
};

void solve(){   
    node <int> segtree(0, 0, 1e9+5);
    int q;cin>>q;
    int c = 0;
    while(q--){
        int d,x,y;
        cin>>d>>x>>y;
        x+=c;y+=c;
        if(d==1){
            c = segtree.range_query(x,y);
            cout<<c<<"\n";
        }
        else{
            segtree.range_upd(x,y,1);
        }

    }


}


int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t=1; 
    // cin>>t;

    while(t--){
        solve();
    }

    return 0;
}; 

• Subtask 1: 100 / 100