Submission #4824

#	Time	Username	Problem	Language	Result	Execution time	Memory
4824		tncks0121	Monkey and Apple-trees (IZhO12_apple)	C++98	100 / 100	540 ms	167656 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;
	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;
}

• Subtask 1: 100 / 100