oj.uz

Submission #337652

# Submission time Handle Problem Language Result Execution time Memory
337652 2020-12-21T11:13:07 Z tengiz05 Weighting stones (IZhO11_stones) C++17
0 / 100
 1000 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int n, m, k;
struct segtree{
	struct node{
		int mn, mx;
		int toprop;
	};
	vector<node> t;
	void build(){
		t.assign(n*2, {0,0,0});
	}
	void prop(int x){
		if(x < n)t[x*2].toprop+=t[x].toprop, t[x*2+1].toprop+=t[x].toprop;
		t[x].mn += t[x].toprop;
		t[x].mx += t[x].toprop;
		t[x].toprop=0;
	}
	void app(int x){
		vector<int> tmp;
		while(x){
			tmp.pb(x);
			x>>=1;
		}reverse(all(tmp));
		for(auto xx : tmp)prop(xx);
	}
	void fix(int x){
		while(x){
			prop(x);
			prop(x*2);
			prop(x*2+1);
			t[x].mn = min(t[x*2].mn, t[x*2+1].mn);
			t[x].mx = max(t[x*2].mx, t[x*2+1].mx);
			x>>=1;
		}
	}
	void update(int l, int r, int val){
		int tl = l, tr = r;
		l+=n,r+=n;
		app(l);app(r);
		for(;l<=r;l>>=1,r>>=1){
			if(l%2==1)t[l++].toprop += val,prop(l-1);
			if(r%2==0)t[r--].toprop += val,prop(r+1);
		}app(tl+n);app(tr+n);
		fix((tl+n)>>1); fix((tr+n)>>1);
	}
};
void solve(int test_case){
	int i, j;
	cin >> n;
	segtree seg; seg.build();
	for(i=0;i<n;i++){
		int w, s;
		cin >> w >> s;
		if(s == 1)seg.update(0, w-1, 1);
		else seg.update(0, w-1, -1);
		for(j=0;j<n;j++)seg.fix((j+n)>>1);
		int mn = seg.t[1].mn;
		int mx = seg.t[1].mx;
		if(mn >= 0){
			cout << ">\n";
		}else if(mx <= 0){
			cout << "<\n";
		}else {
			cout << "?\n";
		}
	}
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 5 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 14 ms 364 KB Output is correct
6 Correct 24 ms 364 KB Output is correct
7 Correct 100 ms 428 KB Output is correct
8 Correct 169 ms 384 KB Output is correct
9 Correct 133 ms 364 KB Output is correct
10 Execution timed out 1080 ms 512 KB Time limit exceeded
11 Halted 0 ms 0 KB -