Submission #959683

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959683	2024-04-08T18:35:11 Z	vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++	100 / 100	381 ms	202832 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1000000000;
const int NIL = -1;

class SparseSegmentTree{
  public:
  SparseSegmentTree(int number_of_datum){
    n = 1;
    while(n < number_of_datum) n *= 2;
    root = new Node(0, n);
  }
  void range_update(int s, int t){
    inner_add(s, t + 1, root);
  }
  int range_query(int s, int t){
    return inner_getsum(s, t + 1, root);
  }
  private:
  struct Node{
    int left_bound, right_bound;
    int dat, laz = NIL;
    Node *left_child, *right_child;
    Node(int lb, int rb){
      left_bound = lb;
      right_bound = rb;
    }
  };
  void inner_split(Node *node){
    if(node->left_child) return;
    int l = node->left_bound;
    int r = node->right_bound;
    if(l + 1 == r) return;
    int mid = (l + r) / 2;
    node->left_child = new Node(l, mid);
    node->right_child = new Node(mid, r);
  }
  void inner_prop(Node *node){
    inner_split(node);
    if(!node->left_child) return;
    if(node->laz == NIL) return;
    node->left_child->dat = node->laz / 2;
    node->right_child->dat = node->laz / 2;
    node->left_child->laz = node->laz / 2;
    node->right_child->laz = node->laz / 2;
    node->laz = NIL;
  }
  void inner_add(int a, int b, Node *node){
    int l = node->left_bound;
    int r = node->right_bound;
    if(b <= l || r <= a) return;
    if(a <= l && r <= b){
      node->dat = r - l;
      node->laz = r - l;
      return;
    }
    inner_prop(node);
    if(!node->left_child) return;
    inner_add(a, b, node->left_child);
    inner_add(a, b, node->right_child);
    node->dat = node->left_child->dat + node->right_child->dat;
  }
  int inner_getsum(int a, int b, Node *node){
    if(!node) return 0;
    int l = node->left_bound;
    int r = node->right_bound;
    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return node->dat;
    inner_prop(node);
    return inner_getsum(a, b, node->left_child) + inner_getsum(a, b, node->right_child);
  }
  int n;
  Node *root;
};

int q;

int main(){
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> q;
  SparseSegmentTree st(MAX_N);
  int C = 0;
  while(q--){
    int op;
    cin >> op;
    if(op == 2){
      int s, t;
      cin >> s >> t;
      s--;
      t--;
      st.range_update(s + C, t + C);
    }else{
      int s, t;
      cin >> s >> t;
      s--;
      t--;
      int res = st.range_query(s + C, t + C);
      cout << res << endl;
      C = res;
    }
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	17 ms	4700 KB	Output is correct
5	Correct	17 ms	5724 KB	Output is correct
6	Correct	21 ms	5724 KB	Output is correct
7	Correct	17 ms	5724 KB	Output is correct
8	Correct	115 ms	41816 KB	Output is correct
9	Correct	246 ms	75096 KB	Output is correct
10	Correct	259 ms	80368 KB	Output is correct
11	Correct	259 ms	86388 KB	Output is correct
12	Correct	272 ms	89100 KB	Output is correct
13	Correct	236 ms	105552 KB	Output is correct
14	Correct	238 ms	106328 KB	Output is correct
15	Correct	381 ms	194364 KB	Output is correct
16	Correct	356 ms	195920 KB	Output is correct
17	Correct	251 ms	110080 KB	Output is correct
18	Correct	243 ms	110164 KB	Output is correct
19	Correct	375 ms	202612 KB	Output is correct
20	Correct	363 ms	202832 KB	Output is correct