Submission #989609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989609	2024-05-28T12:01:44 Z	tch1cherin	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	278 ms	207700 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	4956 KB	Output is correct
5	Correct	10 ms	5980 KB	Output is correct
6	Correct	10 ms	5724 KB	Output is correct
7	Correct	10 ms	5980 KB	Output is correct
8	Correct	91 ms	43816 KB	Output is correct
9	Correct	161 ms	75600 KB	Output is correct
10	Correct	167 ms	83536 KB	Output is correct
11	Correct	188 ms	89936 KB	Output is correct
12	Correct	174 ms	92752 KB	Output is correct
13	Correct	157 ms	108116 KB	Output is correct
14	Correct	166 ms	109144 KB	Output is correct
15	Correct	270 ms	199904 KB	Output is correct
16	Correct	277 ms	203348 KB	Output is correct
17	Correct	204 ms	114768 KB	Output is correct
18	Correct	163 ms	114772 KB	Output is correct
19	Correct	269 ms	207700 KB	Output is correct
20	Correct	278 ms	207696 KB	Output is correct