oj.uz

Submission #901232

# Submission time Handle Problem Language Result Execution time Memory
901232 2024-01-09T08:10:35 Z LCJLY Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 302 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,1e9+5);
	
	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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 15 ms 8000 KB Output is correct
5 Correct 12 ms 9560 KB Output is correct
6 Correct 12 ms 9164 KB Output is correct
7 Correct 12 ms 9560 KB Output is correct
8 Correct 116 ms 72440 KB Output is correct
9 Correct 271 ms 125824 KB Output is correct
10 Correct 232 ms 138852 KB Output is correct
11 Correct 262 ms 149328 KB Output is correct
12 Correct 263 ms 154132 KB Output is correct
13 Correct 233 ms 179496 KB Output is correct
14 Correct 265 ms 181188 KB Output is correct
15 Runtime error 302 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -