Submission #989609

#	Time	Username	Problem	Language	Result	Execution time	Memory
989609		tch1cherin	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	278 ms	207700 KiB

apple

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

struct segment_tree {
  int lx, rx, value = 0, push = 0;
  segment_tree* left = nullptr;
  segment_tree* right = nullptr;

  segment_tree(int _lx, int _rx) : lx(_lx), rx(_rx) {}

  void extend() {
    if (!left) {
      int mid = (lx + rx) / 2;
      left = new segment_tree(lx, mid);
      right = new segment_tree(mid, rx);
    }
  }

  void propagate() {
    if (push) {
      int mid = (lx + rx) / 2;
      left->value = mid - lx, left->push = 1;
      right->value = rx - mid, right->push = 1;
      push = 0;
    }
  }

  void update(int l, int r) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      value = rx - lx;
      push = 1;
    } else {
      extend(), propagate();
      int mid = (lx + rx) / 2;
      left->update(l, r);
      right->update(l, r);
      value = left->value + right->value;
    }
  }

  int query(int l, int r) {
    if (lx >= r || rx <= l) {
      return 0;
    } else if (lx >= l && rx <= r) {
      return value;
    } else {
      extend(), propagate();
      return left->query(l, r) + right->query(l, r);
    }
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int M;
  cin >> M;
  segment_tree ST(1, 1e9 + 1);
  int C = 0;
  for (int i = 0; i < M; i++) {
    int D, X, Y;
    cin >> D >> X >> Y;
    if (D == 1) {
      cout << (C = ST.query(X += C, 1 + (Y += C))) << "\n";
    } else {
      ST.update(X += C, 1 + (Y += C));
    }
  }
}

Compilation message (stderr)

apple.cpp: In member function 'void segment_tree::update(int, int)':
apple.cpp:36:11: warning: unused variable 'mid' [-Wunused-variable]
   36 |       int mid = (lx + rx) / 2;
      |           ^~~

• Subtask 1: 100 / 100