Submission #164990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
164990	2019-11-24T15:48:50 Z	shashwatchandra	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	675 ms	262148 KB

apple

/*input
6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
 
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;
 
int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}
 
int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}
 
int ceil1(int n,int k){
    return floor1(n+k-1,k);
}
 
struct node{
	node* left,*right;
	int cnt;
	bool lazy = 0;
	node(){
		cnt = 0;
		lazy = 0;
		left = NULL;
		right = NULL;
	}
	void extend(){
		left = new node();
		right = new node();
	}
};
 
node* root = new node();
 
inline void pushdown(node* cur,int l,int r){
	if(cur->lazy)cur->cnt = r-l+1;
	if(l != r and cur->lazy){
		if(cur->left == NULL)cur->extend();
		cur->left->lazy = 1;
		cur->right->lazy = 1;
	}
	cur->lazy = 0;
}
 
#define mid (l+r)/2
 
void upd(node* cur,int l,int r,int start,int end){
	pushdown(cur,l,r);
	if(l > end or start > r)return;
	if(start<= l and r <= end){
		cur->lazy = 1;
		pushdown(cur,l,r);
		return;
	}
	if(cur->left == NULL)cur->extend();
	upd(cur->left,l,mid,start,end);
	upd(cur->right,mid+1,r,start,end);
	cur->cnt = cur->left->cnt+cur->right->cnt;
}
 
int query(node *cur,int l,int r,int start,int end){
	pushdown(cur,l,r);
	if(l > end or start > r)return 0;
	if(start<= l and r <= end){
		return cur->cnt;
	}
	if(cur->left == NULL)cur->extend();
	return query(cur->left,l,mid,start,end)+
	query(cur->right,mid+1,r,start,end);
}
 
int upper = 1e9;
int q;
int c = 0;
 
void solve(){
  	cin >> q;
  	while(q--){
  		int ty,x,y;cin >> ty >> x >> y;
  		x += c;
  		y += c;
  		if(ty == 2){
  			upd(root,1,upper,x,y);
  		}
  		else{
  			int ans =query(root,1,upper,x,y);
  			cout << ans << "\n";
  			c = ans;
  		}
  	}
}
 
signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	26 ms	8568 KB	Output is correct
5	Correct	33 ms	10488 KB	Output is correct
6	Correct	33 ms	10104 KB	Output is correct
7	Correct	33 ms	10360 KB	Output is correct
8	Correct	277 ms	77120 KB	Output is correct
9	Correct	540 ms	130936 KB	Output is correct
10	Correct	675 ms	146936 KB	Output is correct
11	Correct	607 ms	159480 KB	Output is correct
12	Correct	635 ms	164956 KB	Output is correct
13	Correct	561 ms	205176 KB	Output is correct
14	Correct	569 ms	207192 KB	Output is correct
15	Runtime error	646 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-