oj.uz

Submission #901272

# Submission time Handle Problem Language Result Execution time Memory
901272 2024-01-09T08:33:43 Z LCJLY Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 208 ms 152604 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;
 
inline int combine(int a, int b){
	return a+b;
}
 
struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int lazySet;
	bool lset;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(0),lazySet(0),lset(0){
	}
	
	inline void inst(){
		if(l==NULL)l=new node(s,m);
		if(r==NULL)r=new node(m+1,e);
	}
	
	void self_set(int x){
		v=(e-s+1)*x;
		lazySet=x;
		lset=1;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lset){
			l->self_set(lazySet),r->self_set(lazySet);
			lazySet=0;
			lset=0;
		}
	}
	
	void rangeSet(int x, int y, int c){
		if(v==e-s+1) return;
		if(x<=s&&y>=e){
			self_set(c);
			return;
		}
		inst();
		forceProp();
		if(x<=m)l->rangeSet(x,y,c);
		if(y>m)r->rangeSet(x,y,c);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		inst();
		forceProp();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};
 
void solve(){	
	int n;
	cin >> n;
	int add=0;
	int temp,temp2,temp3;
	node st(0,1000000005);
	
	for(int x=0;x<n;x++){
		cin >> temp >> temp2 >> temp3;
		temp2+=add;
		temp3+=add;
		if(temp==1){
			add=st.query(temp2,temp3);
			cout << add << "\n";
		}
		else{
			st.rangeSet(temp2,temp3,1);
		}
	}
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 8 ms 4628 KB Output is correct
6 Correct 9 ms 4468 KB Output is correct
7 Correct 9 ms 4828 KB Output is correct
8 Correct 67 ms 35412 KB Output is correct
9 Correct 129 ms 61940 KB Output is correct
10 Correct 140 ms 67476 KB Output is correct
11 Correct 143 ms 71904 KB Output is correct
12 Correct 137 ms 73784 KB Output is correct
13 Correct 127 ms 79188 KB Output is correct
14 Correct 125 ms 78792 KB Output is correct
15 Correct 198 ms 147808 KB Output is correct
16 Correct 194 ms 149296 KB Output is correct
17 Correct 134 ms 83188 KB Output is correct
18 Correct 137 ms 83700 KB Output is correct
19 Correct 206 ms 152604 KB Output is correct
20 Correct 208 ms 152396 KB Output is correct