답안 #477674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477674	2021-10-03T03:09:27 Z	erke	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	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