Submission #31734

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31734	2017-09-03T03:36:28 Z	trath	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	63 ms	2016 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ieps (int) 1e6
#define eps (int) 1e9
#define pii pair<int,int>
int n , x, y;

struct node{
	int soma = 0LL;
	struct node *left , *right;
	node() : left(NULL) , right(NULL) {}
	void pleft(){
		if(!left) left = new node();
	}
	void pright(){
		if(!right) right = new node();
	}
};

node *st = new node();

void update(int x , int y , node *curr = st , int l = 1 , int r = (int) 1e9){
	if(curr->soma == r - l + 1) return;
	if(l == x && r == y){
		curr->soma = y - x + 1;
		return;
	}
	int mid = (l+r)/2;
	if(y <= mid){
		if(!curr->left) curr->pleft();
		update(x , y , curr->left , l , mid);
	}
	else if(x > mid){
		if(!curr->right) curr->pright();
		update(x , y , curr->right , mid + 1 , r);
	}
	else{
		if(!curr->left) curr->pleft();
		if(!curr->right) curr->pright();
		update(x , mid , curr->left , l , mid);
		update(mid + 1 , y , curr->right , mid + 1 , r);
	}
	int qq = 0LL;
	if(curr->left) qq+=curr->left->soma;
	if(curr->right) qq+=curr->right->soma;
	curr->soma = qq;
} 


int getsum(int x , int y , node *curr =  st ,int l = 1 , int r = (int) 1e9){
	if(curr->soma == r - l + 1) return y - x + 1;
	if(l == x && r == y){
		return curr->soma;
	}
	int mid = (l+r)/2;
	if(y <= mid){
		if(!curr->left) return 0;
		return getsum(x , y ,curr->left, l , mid);
	}
	else if(x > mid){
		if(!curr->right) return 0;
		return getsum(x , y , curr->right , mid + 1 , r);
	}
	else{
		int qq = 0LL;
		if(curr->left) qq+=getsum(x , mid , curr->left , l , mid);
		if(curr->right) qq+=getsum(mid + 1 , y , curr->right , mid +1 , r);
		return qq;
	}
}

int q;
int c = 0;
int32_t main(){
	scanf("%d" , &q);
	while(q--){
		scanf("%d%d%d" , &n , &x , &y);
		if(n == 1){
			printf("%d\n" ,  c = getsum(x + c , y + c));
		}
		else{
			update(x + c , y + c);
		}
	}
}

Compilation message

apple.cpp: In function 'int32_t main()':
apple.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &q);
                  ^
apple.cpp:81:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &n , &x , &y);
                                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2016 KB	Output is correct
2	Correct	0 ms	2016 KB	Output is correct
3	Correct	0 ms	2016 KB	Output is correct
4	Correct	3 ms	2016 KB	Output is correct
5	Correct	3 ms	2016 KB	Output is correct
6	Correct	6 ms	2016 KB	Output is correct
7	Correct	6 ms	2016 KB	Output is correct
8	Correct	36 ms	2016 KB	Output is correct
9	Correct	56 ms	2016 KB	Output is correct
10	Correct	56 ms	2016 KB	Output is correct
11	Correct	59 ms	2016 KB	Output is correct
12	Correct	56 ms	2016 KB	Output is correct
13	Correct	63 ms	2016 KB	Output is correct
14	Correct	59 ms	2016 KB	Output is correct
15	Correct	49 ms	2016 KB	Output is correct
16	Correct	53 ms	2016 KB	Output is correct
17	Correct	43 ms	2016 KB	Output is correct
18	Correct	39 ms	2016 KB	Output is correct
19	Correct	53 ms	2016 KB	Output is correct
20	Correct	43 ms	2016 KB	Output is correct