oj.uz

Submission #901171

# Submission time Handle Problem Language Result Execution time Memory
901171 2024-01-09T07:47:42 Z LCJLY Weighting stones (IZhO11_stones) C++14
100 / 100
 76 ms 17288 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 pii combine(pii a, pii b){
	return {max(a.first,b.first),min(a.second,b.second)};
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v;
	int lazyUpd;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v({0,0}),lazyUpd(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_add(int x){
		v.first+=x;
		v.second+=x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd),r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m)l->rangeUpd(x,y,c);
		if(y>m)r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		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 temp,temp2;
	node st(0,n+5);
	
	for(int x=0;x<n;x++){
		cin >> temp >> temp2;
		if(temp2==1){
			st.rangeUpd(1,temp,1);
		}
		else{
			st.rangeUpd(1,temp,-1);
		}
		
		pii hold=st.query(1,n);
		if(hold.first>=0&&hold.second>=0) cout << ">\n";
		else if(hold.first<=0&&hold.second<=0) cout << "<\n";
		else cout << "?\n";
	}
}	

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 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 6 ms 1920 KB Output is correct
11 Correct 45 ms 9560 KB Output is correct
12 Correct 73 ms 15424 KB Output is correct
13 Correct 62 ms 16920 KB Output is correct
14 Correct 61 ms 16932 KB Output is correct
15 Correct 67 ms 17060 KB Output is correct
16 Correct 65 ms 17008 KB Output is correct
17 Correct 69 ms 17288 KB Output is correct
18 Correct 64 ms 16812 KB Output is correct
19 Correct 64 ms 16976 KB Output is correct
20 Correct 62 ms 16976 KB Output is correct
21 Correct 64 ms 17060 KB Output is correct
22 Correct 76 ms 16908 KB Output is correct
23 Correct 64 ms 17084 KB Output is correct
24 Correct 72 ms 17020 KB Output is correct
25 Correct 64 ms 16976 KB Output is correct