Submission #1290068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290068		abdualrimali	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	362 ms	327680 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, lazy, left, right;
    bool is_lazy;
    Node(ll v = 0) : val(v), lazy(0ll), is_lazy(false), left(-1), right(-1) {}
    static Node identity() { return Node(0); }
    static Node merge(const Node &a, const Node &b, int nodeA=0, int nodeB=0) {
        Node ret;
        ret.val = a.val + b.val;
        ret.left=nodeA;
        ret.right=nodeB;
        return ret;
    }
    void apply(ll x, int l, int r){
        val = x * (r-l+1);
        lazy = x;
        is_lazy=true;
    }
    void reset(){
        is_lazy=false;
        lazy=0ll;
    }
};

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;

    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;
        grow(node);
        tree[L].apply(tree[node].lazy, l, MID);
        tree[R].apply(tree[node].lazy, MID+1, r);
        tree[node].reset();
    }

    void update(int l, int r, int node, int lq, int rq, ll val) { 
        propagate(node, l, r); // always propagate before anything 
        if(l>rq || r<lq){
            return;
        }
        if(lq<=l && rq>=r){
            tree[node].apply(val, l, r); // lazy value set
            return;
        }
        grow(node);
        update(l, MID, L, lq, rq, val);
        update(MID+1, r, R, lq, rq, val);
        tree[node] = Node::merge(tree[L], tree[R], L, R);
    }  
    Node query(int l, int r, int node, int lq, int rq) {  
        propagate(node, l, r); // always propagate before anything
        if(l>rq || r<lq) {  
            return Node::identity();  
        }  
        if(l>=lq&&r<=rq) {  
            return tree[node];  
        } 
        grow(node);
        return Node::merge(
                        query(l, MID, L, lq, rq), 
                        query(MID+1, r, R, lq, rq)); 
    }  
public:  
    SparseSegmentTree(int n, int q=0) : sz(n) {
        if (q > 0) { tree.reserve(2 * q * __lg(n)); } 
        tree.push_back(Node()); // root node
    }
    void update(int lq, int rq, ll val) { update(0, sz-1, 0, lq, rq, val);  }  
    Node query(int lq, int rq) { return query(0, sz-1, 0, 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).val;
			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;
    for(int t=1;t<=TC;t++){
        // __TEST_CASE_ID__=t;
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 100