Submission #993162

#	Time	Username	Problem	Language	Result	Execution time	Memory
993162		tch1cherin	Weighting stones (IZhO11_stones)	C++17	100 / 100	67 ms	5456 KiB

stones

#include <bits/stdc++.h>
using namespace std;

struct segment_tree {
  struct node {
    int value, push;
  };

  node merge(node a, node b) {
    return {min(a.value, b.value), 0};
  }
  
  int size;
  vector<node> tree;

  void apply(int x, int value) {
    tree[x].value += value;
    tree[x].push += value;
  }

  void propagate(int x) {
    if (tree[x].push != 0) {
      apply(x * 2, tree[x].push);
      apply(x * 2 + 1, tree[x].push);
      tree[x].push = 0;
    }
  }

  segment_tree(int n) : size(2 << __lg(n)) {
    tree.assign(size * 2, {0, 0});
  }

  void update(int l, int r, int value) {
    update(l, r, value, 1, 0, size);
  }

  void update(int l, int r, int value, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      apply(x, value);
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      update(l, r, value, x * 2, lx, mid);
      update(l, r, value, x * 2 + 1, mid, rx);
      tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }
  }

  int query() {
    return tree[1].value;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  segment_tree T1(N), T2(N);
  for (int i = 0; i < N; i++) {
    int R, S;
    cin >> R >> S;
    if (S == 1) {
      T1.update(0, R, 1);
      T2.update(0, R, -1);
    } else {
      T1.update(0, R, -1);
      T2.update(0, R, 1);
    }
    if (T1.query() >= 0) {
      cout << ">\n";
    } else if (T2.query() >= 0) {
      cout << "<\n";
    } else {
      cout << "?\n";
    }
  }
}

• Subtask 1: 100 / 100