Submission #903263

#	Time	Username	Problem	Language	Result	Execution time	Memory
903263		dsyz	Weighting stones (IZhO11_stones)	C++17	100 / 100	59 ms	10800 KiB

stones

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
struct node{
  int s,e,m,maxv,minv,lazyadd;
  node *l,*r;
  node(int _s,int _e){
    s = _s;
    e = _e;
    m = (s + e) / 2;
    maxv = 0;
    minv = 0;
    lazyadd = 0;
    if(s != e){
      l = new node(s,m);
      r = new node(m + 1,e);
    }
  }
  void value(){
    if(s == e){
      maxv += lazyadd;
      minv += lazyadd;
      lazyadd = 0;
      return;
    }
    maxv += lazyadd;
    minv += lazyadd;
    r->lazyadd += lazyadd;
    l->lazyadd += lazyadd;
    lazyadd = 0;
    return;
  }
  void add(int x,int y,int val){
    if(s == x && e == y) lazyadd += val;
    else{
      if(x > m) r -> add(x,y,val);
      else if(y <= m) l -> add(x,y,val);
      else l -> add(x,m,val), r -> add(m + 1,y,val);
      l->value(), r->value();
      maxv = max(l->maxv,r->maxv);
      minv = min(l->minv,r->minv);
    }
  }
  int rmaxq(){
      value();
      return maxv;
  }
  int rminq(){
      value();
      return minv;
  }
} *root;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	root = new node(0,N - 1);
	for(ll i = 0;i < N;i++){
		ll c,s;
		cin>>c>>s;
		c--;
		if(s == 1){
			root -> add(0,c,1);
		}else if(s == 2){
			root -> add(0,c,-1);
		}
		ll minimum = root -> rminq();
		ll maximum = root -> rmaxq();
		if(maximum <= 0) cout<<'<'<<'\n';
		else if(minimum >= 0) cout<<'>'<<'\n';
		else cout<<'?'<<'\n';
	}
}

• Subtask 1: 100 / 100