Submission #31734

#	Time	Username	Problem	Language	Result	Execution time	Memory
31734		trath	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	63 ms	2016 KiB

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 (stderr)

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 / 100