Submission #164979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
164979	2019-11-24T15:23:35 Z	shashwatchandra	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	744 ms	262144 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();
 
void pushdown(node* cur,int l,int r){
	if(cur->lazy)cur->cnt = r-l+1;
	if(l != r and cur->lazy){
		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){
	if(cur->left == NULL)cur->extend();
	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;
	}
	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){
	if(cur->left == NULL)cur->extend();
	pushdown(cur,l,r);
	if(l > end or start > r)return 0;
	if(start<= l and r <= end){
		return cur->cnt;
	}
	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	28 ms	9464 KB	Output is correct
5	Correct	35 ms	11512 KB	Output is correct
6	Correct	38 ms	11060 KB	Output is correct
7	Correct	36 ms	11384 KB	Output is correct
8	Correct	303 ms	87152 KB	Output is correct
9	Correct	608 ms	150572 KB	Output is correct
10	Correct	744 ms	166664 KB	Output is correct
11	Correct	665 ms	179312 KB	Output is correct
12	Correct	664 ms	184900 KB	Output is correct
13	Correct	582 ms	215296 KB	Output is correct
14	Correct	589 ms	217336 KB	Output is correct
15	Runtime error	641 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-