답안 #4824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4824	2014-01-04T13:35:16 Z	tncks0121	원숭이와 사과 나무 (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

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