Submission #4824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4824	2014-01-04T13:35:16 Z	tncks0121	Monkey and Apple-trees (IZhO12_apple)	C++	100 / 100	540 ms	167656 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;
	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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1204 KB	Output is correct
2	Correct	0 ms	1204 KB	Output is correct
3	Correct	0 ms	1204 KB	Output is correct
4	Correct	16 ms	4768 KB	Output is correct
5	Correct	12 ms	5560 KB	Output is correct
6	Correct	24 ms	5428 KB	Output is correct
7	Correct	20 ms	5560 KB	Output is correct
8	Correct	144 ms	35788 KB	Output is correct
9	Correct	332 ms	63904 KB	Output is correct
10	Correct	312 ms	67600 KB	Output is correct
11	Correct	340 ms	72748 KB	Output is correct
12	Correct	352 ms	74860 KB	Output is correct
13	Correct	340 ms	88588 KB	Output is correct
14	Correct	340 ms	89116 KB	Output is correct
15	Correct	540 ms	162376 KB	Output is correct
16	Correct	532 ms	163828 KB	Output is correct
17	Correct	340 ms	92152 KB	Output is correct
18	Correct	340 ms	92152 KB	Output is correct
19	Correct	468 ms	167656 KB	Output is correct
20	Correct	512 ms	167656 KB	Output is correct