Submission #524645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524645	2022-02-09T17:56:08 Z	Pety	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	508 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;
  short lazy;
  aint *st, *dr;
  aint() {
    st = dr = NULL;
    lazy = -1;
    sum = 0;
  }
}*root;
 
void push (aint* node, int st, int dr) {
  if (node->lazy == -1)
    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 = -1;
} 
 
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	1 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	15 ms	6504 KB	Output is correct
5	Correct	20 ms	7900 KB	Output is correct
6	Correct	19 ms	7612 KB	Output is correct
7	Correct	20 ms	7884 KB	Output is correct
8	Correct	155 ms	58464 KB	Output is correct
9	Correct	319 ms	100932 KB	Output is correct
10	Correct	318 ms	111600 KB	Output is correct
11	Correct	329 ms	120004 KB	Output is correct
12	Correct	332 ms	123816 KB	Output is correct
13	Correct	303 ms	143860 KB	Output is correct
14	Correct	312 ms	145424 KB	Output is correct
15	Runtime error	508 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-