제출 #1290265

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

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;

template <typename T, typename Compare = std::less<T>>
using ordered_set = tree<T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;

const ll MOD = 1e9 + 7;
const long double EPS = 1e-9;

#define all(v) (v).begin(), (v).end()

// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #else
// #define dbg(...)
// #define mark(...)
// #define here(...)
// #define trace_enter(...)
// #define trace_exit(...)
// inline int __TEST_CASE_ID__ = 0;
// struct Timer {void start(...){} void stop(...){}} timer;
// #endif


struct Node { 
    ll val = 0, lazy = 0; 
    bool is_lazy = false; 
    int left = -1, right = -1; 

    void apply(ll x, int l, int r) { 
        val += x; 
        lazy = x; 
        is_lazy = true; 
    } 
    void reset() { is_lazy = false; lazy = 0; } 
}; 

template<typename T = ll> 
struct SparseSegmentTree {  
#define L tree[node].left 
#define R tree[node].right
#define MID ((l+r)>>1)  
private:  
    int sz=1, timer=0;  
    vector<Node> tree;
    T identity;


    inline void grow(int &node) {
        if (L == -1) { L = ++timer; tree.push_back(Node()); }
        if (R == -1) { R = ++timer; tree.push_back(Node()); }
    }
    
    void propagate(int node, int l, int r){
        if(!tree[node].is_lazy || l == r) return;
        tree[L].apply(tree[node].lazy, l, MID);
        tree[R].apply(tree[node].lazy, MID+1, r);
        tree[node].reset();
    }

    void update(int node, int l, int r, int ql, int qr, T val) {
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[node].apply(val, l, r);
            return;
        }
        propagate(node, l, r);
        grow(node);
        update(L, l, MID, ql, qr, val);
        update(R, MID + 1, r, ql, qr, val);
        tree[node].val = tree[L].val + tree[R].val;
    }
    T query(int node, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return identity;
        if (ql <= l && r <= qr) return tree[node].val;
        propagate(node, l, r);
        ll res = 0;
        if (L != -1) res += query(L, l, MID, ql, qr);
        if (R != -1) res += query(R, MID + 1, r, ql, qr);
        return res;
    }
public:  
    SparseSegmentTree(int n, int q=0) : sz(n) {
        if (q > 0) { tree.reserve(100 * q); }
        tree.push_back(Node()); // root node
        identity=0;
    }
    void update(int lq, int rq, T val) { update(0, 0, sz-1, lq, rq, val);  }  
    T query(int lq, int rq) { return query(0, 0, sz-1, lq, rq); }  
#undef L  
#undef R  
#undef MID  
};


void solve() {
    int query_num;
	cin >> query_num;
	const int RANGE_SIZE = 1e9;
	SparseSegmentTree st(RANGE_SIZE + 1, query_num);

	int c = 0;
	for (int i = 0; i < query_num; i++) {
		int type, x, y;
		cin >> type >> x >> y;
		if (type == 1) {
			c = st.query(x + c, y + c);
			cout << c << '\n';
		} else if (type == 2) {
			st.update(x + c, y + c, 1);
		}
	}
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // std::freopen("input.txt", "r", stdin);
    // std::freopen("output.txt", "w", stdout);
    // std::freopen("debug.txt", "w", stderr);
    // #endif

    
    
    int TC = 1;
    // cin >> TC;
    // timer.start("x");
    for(int t=1;t<=TC;t++){
        // __TEST_CASE_ID__=t;
        solve();
    }
    // timer.stop("x");
    return 0;
}

• Subtask 1: 0 / 100