제출 #1263694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263694		Alihan_8	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	138 ms	66672 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const int N = 1e9;

struct SegTree{
	struct Info{
		int lf, rg, val, lazy;
		
		Info(int lf = -1, int rg = -1, int val = 0, int lazy = 0) : lf(lf), rg(rg), val(val), lazy(lazy) {}
	};
	
	vector <Info> seg;
	
	SegTree() : seg(1) {}
	
	void push(int v, int l, int r){
		if ( !seg[v].lazy ) return;
		
		if ( seg[v].lf != -1 ) seg[seg[v].lf].lazy = true;
		if ( seg[v].rg != -1 ) seg[seg[v].rg].lazy = true;
		
		seg[v].val = r - l + 1;
	}
	
	void upd(int v, int l, int r, int tl, int tr){
		push(v, l, r);
		
		if ( l > tr or r < tl ) return;
		
		if ( tl <= l && tr >= r ){
			seg[v].lazy = true; 
			
			push(v, l, r);
			
			return;
		}
		
		int m = (l + r) / 2;
		
		if ( seg[v].lf == -1 ){
			seg[v].lf = size(seg), seg.push_back(Info());
		} 
		
		if ( seg[v].rg == -1 ){
			seg[v].rg = size(seg), seg.push_back(Info());
		}
		
		upd(seg[v].lf, l, m, tl, tr);
		upd(seg[v].rg, m + 1, r, tl, tr);
		
		if ( !seg[v].lazy ) seg[v].val = seg[seg[v].lf].val + seg[seg[v].rg].val;
	}
	
	void upd(int l, int r){ upd(0, 1, N, l, r); }
	
	int get(int v, int l, int r, int tl, int tr){
		if ( v == -1 ) return 0;
		
		push(v, l, r);
		
		if ( l > tr or r < tl ) return 0;
		
		if ( seg[v].lazy ) return min(r, tr) - max(l, tl) + 1;
		
		if ( tl <= l && tr >= r ) return seg[v].val;
		
		int m = (l + r) / 2;
		
		return get(seg[v].lf, l, m, tl, tr) + get(seg[v].rg, m + 1, r, tl, tr);
	}
	
	int qry(int l, int r){ return get(0, 1, N, l, r); }
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int q; cin >> q;
	
	SegTree seg;
	
	int prv = 0;
	
	while ( q-- ){
		int d, x, y; cin >> d >> x >> y;
		
		x += prv, y += prv;
		
		if ( d == 1 ){
			prv = seg.qry(x, y);
			
			cout << prv << '\n';
		} else{
			seg.upd(x, y);
		}
	}
}

• Subtask 1: 100 / 100