Submission #337655

#	Time	Username	Problem	Language	Result	Execution time	Memory
337655		tengiz05	Weighting stones (IZhO11_stones)	C++17	100 / 100	206 ms	3812 KiB

stones

#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*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);
		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;
}

Compilation message (stderr)

stones.cpp: In function 'void solve(int)':
stones.cpp:58:9: warning: unused variable 'j' [-Wunused-variable]
   58 |  int i, j;
      |         ^

• Subtask 1: 100 / 100