제출 #1357520

#제출 시각아이디문제언어결과실행 시간메모리
1357520altern23Weighting stones (IZhO11_stones)C++20
100 / 100
33 ms13020 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

struct Segtree {
      ll l, r, lz = 0;
      pair<ll, ll> val;
      Segtree *lf, *rg;
      
      void build() {
            val = {0, 0};
            if (l == r) return;
            ll mid = (l+r)/2;
            lf = new Segtree(), rg = new Segtree();
            lf->l = l, lf->r = mid;
            rg->l = mid+1, rg->r = r;
            lf->build(), rg->build();
      }

      void push() {
            lf->val.first += lz;
            lf->val.second += lz;
            lf->lz += lz;

            rg->val.first += lz;
            rg->val.second += lz;
            rg->lz += lz;

            lz = 0;
      }

      void update(ll x, ll y, ll z) {
            if (l > y || r < x) return;
            if (l >= x && r <= y) {
                  val.first += z;
                  val.second += z;
                  lz += z;
                  return;
            }
            push();
            lf->update(x, y, z), rg->update(x, y, z);
            val = {min(lf->val.first, rg->val.first), max(lf->val.second, rg->val.second)};
      }

      pair<ll, ll> query() {
            return val;
      }
};

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            ll N; cin >> N;
            Segtree sg;
            sg.l = 1, sg.r = N;
            sg.build();
            for (int i = 1; i <= N; i++) {
                  ll R, S; cin >> R >> S;
                  sg.update(1, R, (S == 1 ? 1 : -1));
                  auto [MN, MX] = sg.query();
                  if (MN < 0 && MX > 0) cout << "?\n";
                  else if (MN < 0) cout << "<\n";
                  else cout << ">\n";
            }
      }
}

/*

*/
#Verdict Execution timeMemoryGrader output
Fetching results...