Submission #524644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524644	2022-02-09T17:50:18 Z	Pety	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	525 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, 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	312 KB	Output is correct
4	Correct	15 ms	6456 KB	Output is correct
5	Correct	20 ms	7892 KB	Output is correct
6	Correct	19 ms	7608 KB	Output is correct
7	Correct	20 ms	7736 KB	Output is correct
8	Correct	151 ms	58940 KB	Output is correct
9	Correct	304 ms	102232 KB	Output is correct
10	Correct	321 ms	113060 KB	Output is correct
11	Correct	341 ms	121308 KB	Output is correct
12	Correct	341 ms	125196 KB	Output is correct
13	Correct	310 ms	145668 KB	Output is correct
14	Correct	310 ms	147048 KB	Output is correct
15	Runtime error	525 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-