Submission #881920

#	Time	Username	Problem	Language	Result	Execution time	Memory
881920		dosts	Weighting stones (IZhO11_stones)	C++17	100 / 100	47 ms	10096 KiB

stones

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 1e5+1,inf = 1e18;

struct Node {
  int x,y;
};
struct Upd {
  int x;
};
Node merge(Node a,Node b) {
  return {min(a.x,b.x),max(a.y,b.y)};
}
Upd merge(Upd a,Upd b) {
  return {a.x+b.x};
}
vector<Node> t(4*N);
vector<Upd> lazy(4*N);

void build(int node,int l,int r) {
  if (l == r){
    t[node].x = 0;
    t[node].y = 0;
    lazy[node].x = 0;
    return;
  }
  int m =(l+r) >> 1;
  build(2*node,l,m);
  build(2*node+1,m+1,r);
  t[node] = merge(t[2*node],t[2*node+1]);
}

void apply(int node) {
  t[node].x += lazy[node].x;
  t[node].y += lazy[node].x;
}

void push(int node,bool l) {
  apply(node);
  if (!l) {
    lazy[2*node] = merge(lazy[2*node],lazy[node]);
    lazy[2*node+1] = merge(lazy[2*node+1],lazy[node]);
  }
  lazy[node].x = 0;
}

Node query(int node,int l,int r,int p) {
  push(node,l==r);
  if (l>p || r < p) return {inf,-inf};
  if (l>=p && r <= p) return t[node];
  int m =(l+r) >> 1;
  return merge(query(2*node,l,m,p),query(2*node+1,m+1,r,p));
}

void update(int node,int l,int r,int L,int R,Upd v) {
  push(node,l==r);
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    lazy[node] = merge(lazy[node],v);
    push(node,l==r);
    return;
  }
  int m =(l+r) >> 1;
  update(2*node,l,m,L,R,v);
  update(2*node+1,m+1,r,L,R,v);
  t[node] = merge(t[2*node],t[2*node+1]);
}


void solve() {
  int n;
  cin >> n;
  build(1,1,n);
  F(i,n) {
    int v,p;
    cin >> v >> p;
    if (p == 1) update(1,1,n,1,v,{+1});
    else update(1,1,n,1,v,{-1});
    push(1,n==1);
    if (t[1].x <= 0 && t[1].y <= 0) {
      cout << "<\n";
    }
    else if (t[1].x >= 0 && t[1].y >= 0) {
      cout << ">\n";
    }
    else cout << "?\n";
  }
}	
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout);
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

• Subtask 1: 100 / 100