# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
39302 | 2018-01-11T05:12:49 Z | chonka | Monkey and Apple-trees (IZhO12_apple) | C++ | 716 ms | 262144 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 ( ) ; 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2036 KB | Output is correct |
2 | Correct | 0 ms | 2036 KB | Output is correct |
3 | Correct | 0 ms | 2036 KB | Output is correct |
4 | Correct | 26 ms | 10352 KB | Output is correct |
5 | Correct | 23 ms | 12068 KB | Output is correct |
6 | Correct | 36 ms | 11672 KB | Output is correct |
7 | Correct | 16 ms | 12068 KB | Output is correct |
8 | Correct | 279 ms | 78464 KB | Output is correct |
9 | Correct | 663 ms | 131924 KB | Output is correct |
10 | Correct | 716 ms | 148028 KB | Output is correct |
11 | Correct | 613 ms | 160436 KB | Output is correct |
12 | Correct | 663 ms | 165980 KB | Output is correct |
13 | Correct | 636 ms | 205976 KB | Output is correct |
14 | Correct | 543 ms | 207956 KB | Output is correct |
15 | Memory limit exceeded | 653 ms | 262144 KB | Memory limit exceeded |
16 | Halted | 0 ms | 0 KB | - |