답안 #168231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168231	2019-12-12T03:54:26 Z	abil	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	483 ms	159772 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	156976 KB	Output is correct
2	Correct	130 ms	156820 KB	Output is correct
3	Correct	130 ms	156920 KB	Output is correct
4	Correct	144 ms	157048 KB	Output is correct
5	Correct	152 ms	157048 KB	Output is correct
6	Correct	148 ms	157136 KB	Output is correct
7	Correct	148 ms	157048 KB	Output is correct
8	Correct	261 ms	158016 KB	Output is correct
9	Correct	426 ms	159312 KB	Output is correct
10	Correct	415 ms	159156 KB	Output is correct
11	Correct	418 ms	159280 KB	Output is correct
12	Correct	427 ms	159232 KB	Output is correct
13	Correct	389 ms	159772 KB	Output is correct
14	Correct	388 ms	159736 KB	Output is correct
15	Correct	483 ms	159692 KB	Output is correct
16	Correct	473 ms	159736 KB	Output is correct
17	Correct	393 ms	159608 KB	Output is correct
18	Correct	394 ms	159636 KB	Output is correct
19	Correct	477 ms	159772 KB	Output is correct
20	Correct	481 ms	159676 KB	Output is correct