Submission #39310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
39310	2018-01-11T06:06:51 Z	chonka	Monkey and Apple-trees (IZhO12_apple)	C++	100 / 100	546 ms	215872 KB

apple

#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 ) ;
                                        ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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