Submission #477674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477674	2021-10-03T03:09:27 Z	erke	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	389 ms	137312 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct node {
  int val = 0, laz = 0;
  node *lf = NULL, *ri = NULL;
};

void chNode(node *&curNode) {
  if (curNode == NULL) {
    curNode = new node();
  }
}

struct SPT {
  int n; node rootNode;
  SPT(int n): n(n) {}
  void down(node* curNode, int l, int m, int r) {
    if (!curNode->laz) return;
    curNode->lf->val = m - l + 1;
    curNode->lf->laz = 1;
    curNode->ri->val = r - m;
    curNode->ri->laz = 1;
    curNode->laz = 0;
  }
  void update(node* curNode, int l, int r, int u, int v) {
    if (r < u || l > v) return;
    if (l >= u && r <= v) {
      curNode->val = r - l + 1;
      curNode->laz = 1;
      return;
    }
    int m = (l + r) / 2;
    chNode(curNode->lf);
    chNode(curNode->ri);
    down(curNode, l, m, r);
    update(curNode->lf, l, m, u, v);
    update(curNode->ri, m + 1, r, u, v);
    curNode->val = curNode->lf->val + curNode->ri->val;
  }
  int get(node* curNode, int l, int r, int u, int v) {
    if (r < u || l > v) return 0;
    if (l >= u && r <= v) {
      return curNode->val;
    }
    int m = (l + r) / 2;
    chNode(curNode->lf);
    chNode(curNode->ri);
    down(curNode, l, m, r);
    return get(curNode->lf, l, m, u, v) + get(curNode->ri, m + 1, r, u, v);
  }
  void update(int u, int v) {
    update(&rootNode, -n, n, u, v);
  }
  int get(int u, int v) {
    return get(&rootNode, -n, n, u, v);
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int q; cin >> q;
  SPT spt(1e9);
  int c = 0;
  while (q--) {
    int d, x, y;
    cin >> d >> x >> y;
    if (d == 1) {
      cout << (c = spt.get(x + c, y + c)) << '\n';
    }
    else {
      spt.update(x + c, y + c);
    }
  }
}

Subtask #1

100.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	0 ms	204 KB	Output is correct
4	Correct	12 ms	3292 KB	Output is correct
5	Correct	15 ms	4044 KB	Output is correct
6	Correct	14 ms	3800 KB	Output is correct
7	Correct	16 ms	3932 KB	Output is correct
8	Correct	112 ms	29248 KB	Output is correct
9	Correct	244 ms	50612 KB	Output is correct
10	Correct	239 ms	55936 KB	Output is correct
11	Correct	254 ms	60100 KB	Output is correct
12	Correct	269 ms	62076 KB	Output is correct
13	Correct	241 ms	72132 KB	Output is correct
14	Correct	233 ms	72800 KB	Output is correct
15	Correct	379 ms	133304 KB	Output is correct
16	Correct	375 ms	134244 KB	Output is correct
17	Correct	249 ms	75336 KB	Output is correct
18	Correct	247 ms	75336 KB	Output is correct
19	Correct	381 ms	137312 KB	Output is correct
20	Correct	389 ms	137236 KB	Output is correct