Submission #524655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524655	2022-02-09T18:16:02 Z	Pety	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	549 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;
  if (node->st == NULL) node->st = new aint;
  if (node->dr == NULL) node->dr = new aint;
  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;
  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	0 ms	312 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	16 ms	6460 KB	Output is correct
5	Correct	19 ms	7764 KB	Output is correct
6	Correct	22 ms	7636 KB	Output is correct
7	Correct	19 ms	7728 KB	Output is correct
8	Correct	161 ms	58372 KB	Output is correct
9	Correct	316 ms	100756 KB	Output is correct
10	Correct	335 ms	111548 KB	Output is correct
11	Correct	344 ms	119880 KB	Output is correct
12	Correct	353 ms	123672 KB	Output is correct
13	Correct	318 ms	144032 KB	Output is correct
14	Correct	319 ms	145268 KB	Output is correct
15	Runtime error	549 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-