답안 #470794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470794	2021-09-05T15:41:57 Z	zxcvbnm	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	537 ms	251020 KB

apple

    #define _CRT_SECURE_NO_WARNINGS

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <memory.h>
    #include <math.h>
    #include <assert.h>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include <algorithm>
    #include <string>
    #include <functional>
    #include <vector>
    #include <deque>
    #include <utility>
    #include <bitset>
    #include <limits.h>
    #include <time.h>

    using namespace std;
    typedef long long ll;
    typedef unsigned long long llu;
    typedef double lf;
    typedef unsigned int uint;
    typedef long double llf;
    typedef pair<int, int> pii;

    int Q;

    struct node {
    	int sum, tag, l = 0, r = 0;
    	node *left, *right;
    	node(int sum = 0, int tag = 0): sum(0), tag(0) { left = NULL; right = NULL; }
    };

    node *root;

    void spread (node *nd, int len) {
    	if(nd->tag != 0) {
    		if(nd->left == NULL) nd->left = new node;
    		nd->left->sum =	len / 2;
    		nd->left->tag = 1;

    		if(nd->right == NULL) nd->right = new node;
    		nd->right->sum = len / 2;
    		nd->right->tag = 1;

    		nd->sum = len;
    		nd->tag = 0;
    	}
    }

    int count (node *nd, int nl, int nr, int x, int y) {
    	if(nd == NULL) return 0;

    	int nmid = (nl + nr) >> 1;
    	int ret = 0;

    	spread(nd, nr - nl + 1);
    	if(x <= nl && nr <= y) return nd->sum;
    	if(x <= nmid) ret += count(nd->left,  nl,   nmid, x, min(y, nmid));
    	if(nmid <  y) ret += count(nd->right, nmid+1, nr, max(x, nmid+1), y);
    	return ret;
    }

    int count (int x, int y) {
    	return count(root, 1, 1<<30, x, y);
    }

    void update (node *nd, int nl, int nr, int x, int y) {
    	int nmid = (nl + nr) >> 1;

    	if(x <= nl && nr <= y) {
    		nd->tag = 1;
    		nd->sum = nr - nl + 1;
    		return;
    	}

    	spread(nd, nr-nl+1);

    	if(x <= nmid) {
    		if(nd->left == NULL) nd->left = new node;
    		update(nd->left,  nl,   nmid, x, min(y, nmid));
    	}

    	if(nmid < y) {
    		if(nd->right == NULL) nd->right = new node;
    		update(nd->right, nmid+1, nr, max(x, nmid+1), y);
    	}

    	nd->sum = 0;
    	if(nd->left  != NULL) nd->sum += nd->left->sum;
    	if(nd->right != NULL) nd->sum += nd->right->sum;
    }

    void update (int x, int y) {
    	update(root, 1, 1<<30, x, y);
    }

    int main() {
    	int i, j, k;

    	scanf("%d", &Q);

    	root = new node;

    	int c = 0;

    	while(Q--) {
    		int d, x, y; scanf("%d%d%d", &d, &x, &y);
    		x += c; y += c;
    		if(d == 1) {
    			c = count(x, y);
    			printf("%d\n", c);
    		}else {
    			update(x, y);
    		}
    	}

    	return 0;
    }

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:104:10: warning: unused variable 'i' [-Wunused-variable]
  104 |      int i, j, k;
      |          ^
apple.cpp:104:13: warning: unused variable 'j' [-Wunused-variable]
  104 |      int i, j, k;
      |             ^
apple.cpp:104:16: warning: unused variable 'k' [-Wunused-variable]
  104 |      int i, j, k;
      |                ^
apple.cpp:106:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |      scanf("%d", &Q);
      |      ~~~~~^~~~~~~~~~
apple.cpp:113:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |       int d, x, y; scanf("%d%d%d", &d, &x, &y);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	276 KB	Output is correct
4	Correct	17 ms	5708 KB	Output is correct
5	Correct	20 ms	6972 KB	Output is correct
6	Correct	19 ms	6632 KB	Output is correct
7	Correct	20 ms	6916 KB	Output is correct
8	Correct	155 ms	52568 KB	Output is correct
9	Correct	321 ms	94964 KB	Output is correct
10	Correct	326 ms	100420 KB	Output is correct
11	Correct	337 ms	108140 KB	Output is correct
12	Correct	406 ms	111428 KB	Output is correct
13	Correct	307 ms	132112 KB	Output is correct
14	Correct	342 ms	132912 KB	Output is correct
15	Correct	498 ms	243116 KB	Output is correct
16	Correct	516 ms	245168 KB	Output is correct
17	Correct	348 ms	137452 KB	Output is correct
18	Correct	315 ms	137444 KB	Output is correct
19	Correct	537 ms	250948 KB	Output is correct
20	Correct	524 ms	251020 KB	Output is correct