oj.uz

답안 #707896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707896 2023-03-10T11:30:07 Z Koful123 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 337 ms 200076 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
struct node{
	int sum,lazy,l,r,tl,tr;
	node(): sum(0), lazy(0), l(0), r(0), tl(1), tr(1e9) {};
};
 
struct SegTree{
	vector<node> seg;
	SegTree(){
		seg.pb(node());
	};
	void push(int v,int tl,int tr){
		int tm = (tl + tr) / 2;
		if(seg[v].l == 0){
			seg[v].l = seg.size();
			seg.pb(node());
			seg[seg[v].l].tl = tl;
			seg[seg[v].l].tr = tm;
			
			seg[v].r = seg.size();
			seg.pb(node());
			seg[seg[v].r].tl = tm + 1;
			seg[seg[v].r].tr = tr;
        }
		assert(seg[v].r < seg.size());
		if(!seg[v].lazy) return;
		seg[seg[v].r].lazy = seg[v].lazy;
		seg[seg[v].r].sum = seg[v].lazy * (tr - tm);	
		seg[seg[v].l].lazy = seg[v].lazy;
		seg[seg[v].l].sum = seg[v].lazy * (tm - tl + 1);	
		seg[v].lazy = 0;
	}
	void upd(int v,int l,int r,int tl,int tr,int x){
		if(tl > r || tr < l) return;
		if(tl >= l && tr <= r){
			seg[v].sum = (tr - tl + 1) * x; 
			seg[v].lazy = x;
			return;
		};
		push(v,tl,tr);
		int tm = (tl + tr) / 2;
		upd(seg[v].l,l,r,tl,tm,x), upd(seg[v].r,l,r,tm+1,tr,x);
		seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tl > r || tr < l) return 0;
		if(tl >= l && tr <= r){
			return seg[v].sum;
		}
		push(v,tl,tr);
		int tm = (tl + tr) / 2;
		return get(seg[v].l,tl,tm,l,r) + get(seg[v].r,tm+1,tr,l,r); 
	}
	int get(int l,int r){
		return get(0,1,1e9,l,r);
	}
};
 
void solve(){
 
	SegTree seg;
 
	int q,c = 0; cin >> q;
	for(int i = 0; i < q; i++){
		int ty,l,r; cin >> ty >> l >> r;
		if(ty == 2){
			seg.upd(0,l + c,r + c,1,1e9,1);
		}
		else{
			int res = seg.get(l+c,r+c);
			cout << res << endl; c = res;
		}
	}
}
 
signed main(){
 
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from apple.cpp:1:
apple.cpp: In member function 'void SegTree::push(int, int, int)':
apple.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   assert(seg[v].r < seg.size());

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 3612 KB Output is correct
5 Correct 14 ms 3648 KB Output is correct
6 Correct 14 ms 3712 KB Output is correct
7 Correct 14 ms 3656 KB Output is correct
8 Correct 99 ms 25812 KB Output is correct
9 Correct 212 ms 51036 KB Output is correct
10 Correct 216 ms 50872 KB Output is correct
11 Correct 227 ms 50816 KB Output is correct
12 Correct 220 ms 50988 KB Output is correct
13 Correct 218 ms 101480 KB Output is correct
14 Correct 222 ms 101324 KB Output is correct
15 Correct 336 ms 200076 KB Output is correct
16 Correct 335 ms 200072 KB Output is correct
17 Correct 218 ms 101396 KB Output is correct
18 Correct 221 ms 101400 KB Output is correct
19 Correct 329 ms 199988 KB Output is correct
20 Correct 337 ms 200036 KB Output is correct