답안 #39310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39310 2018-01-11T06:06:51 Z chonka 원숭이와 사과 나무 (IZhO12_apple) C++
100 / 100
546 ms 215872 KB
#include<iostream>
#include<stdio.h>
using namespace std ;


struct Tree {
	int IL , IR ;
	int val ;
	int lazy ;
	Tree *pl , *pr ;
	Tree ( int x , int y ) {
		this->IL = x ;
		this->IR = y ;
		this->lazy = 0 ;
		this->val = 0 ;
		this->pl = this->pr = NULL ;
	}
	void push ( ) {
		if ( this->IL == this->IR ) { return ; }
		if ( this->pl != NULL ) { return ; }
		int mid = ( this->IL + this->IR ) / 2 ;
		this->pl = new Tree ( this->IL , mid ) ;
		this->pr = new Tree ( mid + 1 , this->IR ) ;
	}
	void push_lazy ( ) {
		if ( this->lazy == 0 ) { return ; }
		this->val = ( this->IR - this->IL + 1 ) ;
		if ( this->IL != this->IR ) {
			this->pl->lazy = 1 ;
			this->pr->lazy = 1 ;
		}
		this->lazy = 0 ;
	}
	void recalc ( ) {
		this->pl->push_lazy ( ) ;
		this->pr->push_lazy ( ) ;
		this->val = this->pl->val + this->pr->val ;
	}
	void update ( int x , int y ) {
		this->push ( ) ;
		if ( this->lazy == 1 ) { return ; }
		this->push_lazy ( ) ;
		if ( this->IR < x || y < this->IL ) { return ; }
		if ( x <= this->IL && this->IR <= y ) {
			this->lazy = 1 ;
			this->push_lazy ( ) ;
			return ;
		}
		this->pl->update ( x , y ) ;
		this->pr->update ( x , y ) ;
		this->recalc ( ) ;
	}
	int query ( int x , int y ) {
		if ( this == NULL ) { return 0 ; }
		this->push ( ) ;
		this->push_lazy ( ) ;
		if ( this->IR < x || y < this->IL ) { return 0 ; }
		if ( x <= this->IL && this->IR <= y ) { return this->val ; }
		return this->pl->query ( x , y ) + this->pr->query ( x , y ) ;
	}
};

Tree *root ;

int main ( ) {
	root = new Tree ( 1 , 1000000000 ) ;
	int q ;
	scanf ( "%d" , &q ) ;
	int type , x , y ;
	int c = 0 ;
	while ( q != 0 ) {
		q -- ;
		scanf ( "%d%d%d" , &type , &x , &y ) ;
		x += c ;
		y += c ;
		if ( type == 2 ) {
			root->update ( x , y ) ;
		}
		else {
			c = root->query ( x , y ) ;
			printf ( "%d\n" , c ) ;
		}
	}
	return 0 ;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ( "%d" , &q ) ;
                      ^
apple.cpp:73:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ( "%d%d%d" , &type , &x , &y ) ;
                                        ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 13 ms 6916 KB Output is correct
5 Correct 23 ms 8104 KB Output is correct
6 Correct 23 ms 7708 KB Output is correct
7 Correct 19 ms 8104 KB Output is correct
8 Correct 179 ms 49288 KB Output is correct
9 Correct 369 ms 83872 KB Output is correct
10 Correct 286 ms 92188 KB Output is correct
11 Correct 319 ms 98656 KB Output is correct
12 Correct 296 ms 101560 KB Output is correct
13 Correct 316 ms 114364 KB Output is correct
14 Correct 303 ms 113836 KB Output is correct
15 Correct 519 ms 208876 KB Output is correct
16 Correct 546 ms 210988 KB Output is correct
17 Correct 319 ms 117400 KB Output is correct
18 Correct 303 ms 117796 KB Output is correct
19 Correct 493 ms 215872 KB Output is correct
20 Correct 486 ms 215740 KB Output is correct