oj.uz

Submission #881897

# Submission time Handle Problem Language Result Execution time Memory
881897 2023-12-02T08:18:37 Z vjudge1 Weighting stones (IZhO11_stones) C++17
100 / 100
 50 ms 10840 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 4 ms 9976 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 3 ms 9872 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 26 ms 10332 KB Output is correct
12 Correct 50 ms 10836 KB Output is correct
13 Correct 43 ms 10840 KB Output is correct
14 Correct 43 ms 10588 KB Output is correct
15 Correct 42 ms 10588 KB Output is correct
16 Correct 43 ms 10696 KB Output is correct
17 Correct 41 ms 10588 KB Output is correct
18 Correct 42 ms 10704 KB Output is correct
19 Correct 42 ms 10744 KB Output is correct
20 Correct 42 ms 10684 KB Output is correct
21 Correct 44 ms 10616 KB Output is correct
22 Correct 43 ms 10588 KB Output is correct
23 Correct 42 ms 10580 KB Output is correct
24 Correct 42 ms 10584 KB Output is correct
25 Correct 41 ms 10616 KB Output is correct