Submission #524646

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524646	2022-02-09T17:57:05 Z	Pety	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	514 ms	262148 KB

apple

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
const int INF = 1e9;
const int MOD = 1e9 + 7;
 
int n;
 
struct aint {
  int sum;
  bool lazy;
  aint *st, *dr;
  aint() {
    st = dr = NULL;
    lazy = 0;
    sum = 0;
  }
}*root;
 
void push (aint* node, int st, int dr) {
  if (node->lazy == 0)
    return;
  node->sum = (dr - st + 1) * node->lazy;
  if (st != dr) {
    if (node->st != NULL)
      node->st->lazy = node->lazy;
    if (node->dr != NULL)
      node->dr->lazy = node->lazy;
  }
  node->lazy = 0;
} 
 
void update (aint* root, int st, int dr, int a, int b) {
  if (root->st == NULL) root->st = new aint;
  if (root->dr == NULL) root->dr = new aint;
  push(root, st, dr);
  if (st > dr || b < st || a > dr)
    return;
  if (a <= st && dr <= b) {
    root->sum = dr - st + 1;
    if (st != dr) {
      root->st->lazy = 1;
      root->dr->lazy = 1;
    }
    return;
  }
  int mij = (st + dr) / 2;
  update(root->st, st, mij, a, b);
  update(root->dr, mij + 1, dr, a, b);
  root->sum = root->st->sum + root->dr->sum;
}
 
int query (aint* root, int st, int dr, int a, int b) {
  if (root == NULL)
    return 0;
  if (root->st == NULL) root->st = new aint;
  if (root->dr == NULL) root->dr = new aint;
  push(root, st, dr);
  if (st > dr || b < st || a > dr)
    return 0;
  if (a <= st && dr <= b) 
    return root->sum;
  int mij = (st + dr) / 2;
  return (query(root->st, st, mij, a, b) + query(root->dr, mij + 1, dr, a, b));
}
 
 
 
int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  root = new aint;
  int c = 0;
  for (int i = 1; i <= n; i++) {
    int d, x, y;
    cin >>d >> x >> y;
    x += c; y += c; 
    if (d == 1) {
      c = query(root, 1, INF, x, y);
      cout << c << "\n";
    }
    else {
      update(root, 1, INF, x, y);
    }
  }
  
  
  return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	18 ms	6356 KB	Output is correct
5	Correct	19 ms	7640 KB	Output is correct
6	Correct	18 ms	7412 KB	Output is correct
7	Correct	19 ms	7692 KB	Output is correct
8	Correct	156 ms	58144 KB	Output is correct
9	Correct	328 ms	100548 KB	Output is correct
10	Correct	332 ms	111312 KB	Output is correct
11	Correct	415 ms	119624 KB	Output is correct
12	Correct	329 ms	123332 KB	Output is correct
13	Correct	309 ms	143572 KB	Output is correct
14	Correct	305 ms	144980 KB	Output is correct
15	Runtime error	514 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-