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
#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);
	}
}
# 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