oj.uz

Submission #901222

# Submission time Handle Problem Language Result Execution time Memory
901222 2024-01-09T08:07:31 Z LCJLY Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 313 ms 262144 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(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,2000000000);
	
	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
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 10 ms 8028 KB Output is correct
5 Correct 12 ms 9568 KB Output is correct
6 Correct 12 ms 9176 KB Output is correct
7 Correct 12 ms 9568 KB Output is correct
8 Correct 108 ms 72348 KB Output is correct
9 Correct 222 ms 125776 KB Output is correct
10 Correct 237 ms 138840 KB Output is correct
11 Correct 243 ms 149336 KB Output is correct
12 Correct 246 ms 154112 KB Output is correct
13 Correct 227 ms 179496 KB Output is correct
14 Correct 229 ms 181072 KB Output is correct
15 Runtime error 313 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -