Submission #959681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959681	2024-04-08T18:31:21 Z	vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++	0 / 100	449 ms	262144 KB

apple

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

class SparseSegmentTree{
  public:
  SparseSegmentTree(long long int number_of_datum){
    n = 1;
    while(n < number_of_datum) n *= 2;
    root = new Node(0, n);
  }
  void range_update(long long int s, long long int t){
    inner_add(s, t + 1, root);
  }
  long long int range_query(long long int s, long long int t){
    return inner_getsum(s, t + 1, root);
  }
  private:
  struct Node{
    long long int left_bound, right_bound;
    long long int dat, laz = NIL;
    Node *left_child, *right_child;
    Node(long long int lb, long long int rb){
      left_bound = lb;
      right_bound = rb;
    }
  };
  void inner_split(Node *node){
    if(node->left_child) return;
    long long int l = node->left_bound;
    long long int r = node->right_bound;
    if(l + 1 == r) return;
    long long 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(long long int a, long long int b, Node *node){
    long long int l = node->left_bound;
    long long 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;
  }
  long long int inner_getsum(long long int a, long long int b, Node *node){
    if(!node) return 0;
    long long int l = node->left_bound;
    long long 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);
  }
  long long 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);
  long long int C = 0;
  while(q--){
    int op;
    cin >> op;
    if(op == 2){
      long long int s, t;
      cin >> s >> t;
      s--;
      t--;
      st.range_update(s + C, t + C);
    }else{
      long long int s, t;
      cin >> s >> t;
      s--;
      t--;
      long long int res = st.range_query(s + C, t + C);
      cout << res << endl;
      C = res;
    }
  }
  return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	504 KB	Output is correct
4	Correct	14 ms	6172 KB	Output is correct
5	Correct	18 ms	7512 KB	Output is correct
6	Correct	19 ms	7256 KB	Output is correct
7	Correct	18 ms	7516 KB	Output is correct
8	Correct	127 ms	55636 KB	Output is correct
9	Correct	265 ms	99664 KB	Output is correct
10	Correct	286 ms	106592 KB	Output is correct
11	Correct	278 ms	115028 KB	Output is correct
12	Correct	292 ms	118452 KB	Output is correct
13	Correct	303 ms	140368 KB	Output is correct
14	Correct	260 ms	141620 KB	Output is correct
15	Correct	449 ms	259152 KB	Output is correct
16	Correct	412 ms	262024 KB	Output is correct
17	Correct	269 ms	146524 KB	Output is correct
18	Correct	262 ms	146708 KB	Output is correct
19	Runtime error	408 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-