Submission #168231

#	Time	Username	Problem	Language	Result	Execution time	Memory
168231		abil	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	483 ms	159772 KiB

apple

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_bacak
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long

using namespace std;

const int N = (1e6 + 12);
const int n = (1e9);
const int INF = (0x3f3f3f3f);

struct node{
	int sum, val, l, r;
	node(){
		sum = val = l = r = 0;
	}
};

node t[N * 10];
int cnt = 1;

void push(int v,int l,int r){
	if(!t[v].l){
		t[v].l = ++cnt;
	}
	if(!t[v].r){
		t[v].r = ++cnt;
	}	
	if(t[v].val){
		t[v].sum = r - l + 1;
		t[t[v].l].val = t[t[v].r].val = 1;
		t[v].val = 0;
	}
}

void upd(int v,int tl,int tr,int l,int r){
	push(v, tl, tr);
	if(tl > r || tr < l){
		return;
	}
	if(l <= tl && tr <= r){
		t[v].val = 1;
		push(v, tl, tr);
		return;
	}
	int mid = (tl + tr) >> 1;
	upd(t[v].l, tl, mid, l, r);
	upd(t[v].r, mid + 1, tr, l, r);
	t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
}

int get(int v,int tl,int tr,int l,int r){
	push(v, tl, tr);
	if(tl > r || tr < l){
		return 0;
	}
	if(l <= tl && tr <= r){
		return t[v].sum;
	}
	int mid = (tl + tr) >> 1;
	return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
}
main()
{
	int m, type, l, r, c = 0;
	scanf("%d", &m);
	while(m--){
		scanf("%d%d%d", &type, &l, &r);
		l += c;
		r += c;
		if(type == 2){
			upd(1, 1, n, l, r);
		}
		else{
			c = get(1, 1, n, l, r);
			printf("%d\n", c);
		}
	}
}

Compilation message (stderr)

apple.cpp:67:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
apple.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &type, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100