Submission #17311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17311	2015-11-20T00:41:06 Z	gs14004	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	444 ms	137944 KB

apple

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

struct node{
	node *ls, *rs;
	int sum, lazy;
	node(){
		ls = rs = NULL;
		sum = lazy = 0;
	}
}*root;

void lazydown(node *p, int ps, int pe){
	if(!p->ls) p->ls = new node();
	if(!p->rs) p->rs = new node();
	if(p->lazy == 0) return;
	int pm = (ps+pe)/2;
	p->ls->lazy = 1;
	p->rs->lazy = 1;
	p->ls->sum = pm - ps + 1;
	p->rs->sum = pe - pm;
	p->lazy = 0;
}

void add(int s, int e, int ps, int pe, node *p){
	if(e < ps || pe < s) return;
	if(s <= ps && pe <= e){
		p->sum = pe - ps + 1;
		p->lazy = 1;
		return;
	}
	lazydown(p,ps,pe);
	int pm = (ps + pe) / 2;
	add(s, e, ps, pm, p->ls);
	add(s, e, pm+1, pe, p->rs);
	p->sum = p->ls->sum + p->rs->sum;
}

int sum(int s, int e, int ps, int pe, node *p){
	if(e < ps || pe < s) return 0;
	if(s <= ps && pe <= e) return p->sum;
	lazydown(p,ps,pe);
	int pm = (ps + pe) / 2;
	return sum(s, e, ps, pm, p->ls) + sum(s, e, pm+1, pe, p->rs);
}

int main(){
	int q;
	scanf("%d",&q);
	int c = 0;
	root = new node();
	while(q--){
		int s, e, x;
		scanf("%d %d %d",&x,&s,&e);
		s += c;
		e += c;
		if(x == 1){
			c = sum(s, e, 1, 1e9, root);
			printf("%d\n",c);
		}
		else add(s, e, 1, 1e9, root);
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1720 KB	Output is correct
2	Correct	0 ms	1720 KB	Output is correct
3	Correct	0 ms	1720 KB	Output is correct
4	Correct	14 ms	4624 KB	Output is correct
5	Correct	5 ms	5284 KB	Output is correct
6	Correct	18 ms	5152 KB	Output is correct
7	Correct	14 ms	5284 KB	Output is correct
8	Correct	146 ms	30496 KB	Output is correct
9	Correct	292 ms	51484 KB	Output is correct
10	Correct	278 ms	56896 KB	Output is correct
11	Correct	303 ms	60988 KB	Output is correct
12	Correct	301 ms	62968 KB	Output is correct
13	Correct	283 ms	73000 KB	Output is correct
14	Correct	292 ms	73660 KB	Output is correct
15	Correct	421 ms	133984 KB	Output is correct
16	Correct	443 ms	134908 KB	Output is correct
17	Correct	312 ms	76168 KB	Output is correct
18	Correct	278 ms	76168 KB	Output is correct
19	Correct	432 ms	137944 KB	Output is correct
20	Correct	444 ms	137944 KB	Output is correct