Submission #694717

#	Time	Username	Problem	Language	Result	Execution time	Memory
694717		iskhakkutbilim	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	553 ms	260348 KiB

apple

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1000000000;
int C, Q;
 
struct node{
	node *left, *right;
	int sum, lazy;
	node(){
		left = nullptr, right = nullptr;
		sum = 0, lazy = 0;
	}	
};
typedef node* pnode;
 
void push(pnode &tree, int v, int vl, int vr){
	if(!tree) tree = new node();
	if(tree->lazy == 0) return;
//	cout << vl << ' ' << vr << '\n';
	tree->sum = (vr-vl+1);
	if(vl != vr){
		if(!tree->left) tree->left = new node();
		if(!tree->right) tree->right = new node();
		tree->left->lazy = 1;
		tree->right->lazy = 1;
	}
	tree->lazy = 0;	
}
 
int sum(pnode tree){
	if(tree) return tree->sum;
	return 0;
}
 
void update(pnode &tree, int l, int r, int v, int vl, int vr){
	if(!tree) tree = new node();
	push(tree, v, vl, vr);
	if(l > vr or vl > r) return;
	if(l <= vl and r >= vr){
		tree->lazy = 1;
		push(tree, v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	update(tree->left, l, r, v<<1, vl, mid);
	update(tree->right, l, r, v<<1|1, mid+1, vr);
	tree->sum = sum(tree->left) + sum(tree->right);
}
 
int get_sum(pnode &tree, int l, int r, int v, int vl, int vr){
	if(!tree){
		tree = new node();
	}
	push(tree, v, vl, vr);
	if(l > vr or vl > r) return 0;
	if(l <= vl and r >= vr){
//		cout << tree->sum << " = ";
//		cout << vl << ' ' << vr << '\n';
		return tree->sum;
	}
	int mid = (vl + vr)>>1;
	int s = (tree->left ? get_sum(tree->left,l, r,v<<1, vl, mid) : 0);
	int s1 = (tree->right ? get_sum(tree->right, l, r, v<<1|1, mid+1, vr) : 0);
	tree->sum = sum(tree->left) + sum(tree->right);
	return s+s1;
}
 
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	pnode tree = new node();
	cin >> Q;
	while(Q--){
		int type, l, r; cin >> type >> l >> r;
		if(type == 1){
			C = get_sum(tree, l+C, r+C, 1, 1, N);
			cout << C << '\n';
		}else{
//			cout << l+C << ' ' << r+C << '\n';
			update(tree, l+C, r+C, 1, 1, N);
		}
	}
 
	return 0;
}

Compilation message (stderr)

apple.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~

• Subtask 1: 100 / 100