Submission #1092021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1092021	2024-09-23T00:49:38 Z	juicy	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	128 ms	54260 KB

apple

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int M = 1e9, N = 6000005;

int n = 1;
int s[N], L[N], R[N];

void psh(int id, int l) {
  if (!L[id]) {
    L[id] = ++n;
  }
  if (!R[id]) {
    R[id] = ++n;
  }
  if (s[id] == l) {
    s[L[id]] = (l + 1) / 2;
    s[R[id]] = l / 2;
  }
}

void upd(int u, int v, int id = 1, int l = 1, int r = M) {
  if (u <= l && r <= v) {
    s[id] = r - l + 1;
    return;
  } 
  int m = (l + r) / 2;
  psh(id, r - l + 1);
  if (u <= m) {
    upd(u, v, L[id], l, m);
  }
  if (m < v) {
    upd(u, v, R[id], m + 1, r);
  }
  s[id] = s[L[id]] + s[R[id]];
}

int qry(int u, int v, int id = 1, int l = 1, int r = M) {
  if (u <= l && r <= v) {
    return s[id];
  }
  int m = (l + r) / 2;
  psh(id, r - l + 1);
  if (v <= m) {
    return qry(u, v, L[id], l, m);
  }
  if (m < u) {
    return qry(u, v, R[id], m + 1, r);
  }
  return qry(u, v, L[id], l, m) + qry(u, v, R[id], m + 1, r);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int m; cin >> m;
  int c = 0;
  while (m--) {
    int d, x, y; cin >> d >> x >> y; 
    x += c, y += c;
    if (d == 1) {
      cout << (c = qry(x, y)) << "\n";
    } else {
      upd(x, y);
    }
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	1628 KB	Output is correct
5	Correct	7 ms	1884 KB	Output is correct
6	Correct	8 ms	1884 KB	Output is correct
7	Correct	8 ms	1884 KB	Output is correct
8	Correct	44 ms	12116 KB	Output is correct
9	Correct	90 ms	21120 KB	Output is correct
10	Correct	96 ms	23316 KB	Output is correct
11	Correct	107 ms	24900 KB	Output is correct
12	Correct	99 ms	25592 KB	Output is correct
13	Correct	98 ms	29776 KB	Output is correct
14	Correct	100 ms	29992 KB	Output is correct
15	Correct	128 ms	52720 KB	Output is correct
16	Correct	123 ms	53076 KB	Output is correct
17	Correct	95 ms	31024 KB	Output is correct
18	Correct	96 ms	30800 KB	Output is correct
19	Correct	126 ms	54260 KB	Output is correct
20	Correct	124 ms	54100 KB	Output is correct