Submission #258226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
258226	2020-08-05T15:01:54 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	323 ms	59384 KB

apple

#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>
#include <bitset>
#include <iomanip>
#include <algorithm>
 
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
const int N = 1e9;
 
struct Node {
  Node *l, *r; 
  int sum;
  bool lazy_left;
  bool lazy_right;
  Node () {
    l = r = nullptr;
    sum = 0;
    lazy_left = lazy_right = false;
  }
};
 
Node *root;
 
void push_left (Node *cur, int lo, int hi) {
  if (!cur -> lazy_left) return;
  if (lo != hi) {
    if (cur -> l == nullptr) cur -> l = new Node;
    cur -> l -> sum = (lo + (hi - lo) / 2) - lo + 1;
    cur -> l -> lazy_left = true;
    cur -> l -> lazy_right = true;
  }
  cur -> lazy_left = false;
}
 
void push_right (Node *cur, int lo, int hi) {
  if (!cur -> lazy_right) return;
  if (lo != hi) {
    if (cur -> r == nullptr) cur -> r = new Node;
    cur -> r -> sum = hi - (lo + (hi - lo) / 2);
    cur -> r -> lazy_left = true;
    cur -> r -> lazy_right = true;
  }
  cur -> lazy_right = false;
}
  
int range_query (Node *cur, int ql, int qr, int lo, int hi) {
  if (!cur || lo > qr || hi < ql) return 0;
  if (lo >= ql && hi <= qr) return cur -> sum;
  int res = 0;
  if (lo + (hi - lo) / 2 >= ql) {
    push_left (cur, lo, hi);
    res += range_query (cur -> l, ql, qr, lo, lo + (hi - lo) / 2);
  }
  if (lo + (hi - lo) / 2 + 1 <= qr) {
    push_right (cur, lo, hi);
    res += range_query (cur -> r, ql, qr, lo + (hi - lo) / 2 + 1, hi);
  }
  return res;
}
 
void range_set (Node *cur, int ql, int qr, int lo, int hi) {
  if (cur -> sum == hi - lo + 1) return;
  if (lo > qr || hi < ql) return;
  if (lo >= ql && hi <= qr) {
    cur -> sum = hi - lo + 1;
    cur -> lazy_left = cur -> lazy_right = true;
    return;
  }
  int mid = lo + (hi - lo) / 2;
  if (mid >= ql) {
    if (cur -> l == nullptr) cur -> l = new Node;
    range_set (cur -> l, ql, qr, lo, mid);
  }
  if (mid + 1 <= qr) {
    if (cur -> r == nullptr) cur -> r = new Node;
    range_set (cur -> r, ql, qr, mid + 1, hi);
  }
  push_left (cur, lo, hi); 
  push_right (cur, lo, hi);
  cur -> sum = (cur -> l ? cur -> l -> sum : 0) + (cur -> r ? cur -> r -> sum : 0);
}	
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  root = new Node ();
  int q;
  cin >> q;
  int C = 0;
  while (q--) {
    int task, lo, hi;
    cin >> task >> lo >> hi;
    --lo; --hi;
    lo += C;
    hi += C;
    if (task == 1) {
      // Range Query, update C
      C = range_query (root, lo, hi, 0, N);
      cout << C << '\n';
    } else {
      // Range Set
      range_set (root, lo, hi, 0, N);
    }
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	8 ms	1920 KB	Output is correct
5	Correct	10 ms	2176 KB	Output is correct
6	Correct	11 ms	2048 KB	Output is correct
7	Correct	10 ms	2176 KB	Output is correct
8	Correct	72 ms	14620 KB	Output is correct
9	Correct	140 ms	25848 KB	Output is correct
10	Correct	147 ms	27896 KB	Output is correct
11	Correct	141 ms	29436 KB	Output is correct
12	Correct	145 ms	30200 KB	Output is correct
13	Correct	147 ms	32424 KB	Output is correct
14	Correct	141 ms	32436 KB	Output is correct
15	Correct	199 ms	57568 KB	Output is correct
16	Correct	234 ms	58104 KB	Output is correct
17	Correct	143 ms	33144 KB	Output is correct
18	Correct	144 ms	33272 KB	Output is correct
19	Correct	273 ms	59384 KB	Output is correct
20	Correct	323 ms	59384 KB	Output is correct