Submission #470794

#	Time	Username	Problem	Language	Result	Execution time	Memory
470794		zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	537 ms	251020 KiB

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 (stderr)

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 / 100