Submission #331367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
331367	2020-11-28T06:46:52 Z	ronnith	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	695 ms	262148 KB

apple

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i = (a);i < (b);i ++)
#define FORd(i,b,a) for(int i = (b);i >= (a);i --)
#define trav(a,b) for(auto a:b)
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define sz(a) (a).size()
#define maxn 100000

using ll = long long;
using namespace std;
ll modF = 1e9 + 7;

void setIO(string s = ""){
	ios::sync_with_stdio(0);cin.tie(0);
	if(sz(s)){
		freopen((s + ".in").c_str(),"r",stdin);
		freopen((s + ".out").c_str(),"w",stdout);
	}	
}

int MX = 1e9 + 10;

struct node{
	int val, lazy;
	node *right, *left;
	node():val(0), lazy(0){}
};
struct Segtree{
	node* root;
	Segtree(){
		root = new node();
	}
	void extend(node* crr){
		if(crr->left != nullptr)return;
		crr->left = new node();
		crr->right = new node();
	}
	void propogate(node* crr, int l, int r){
		if(crr->lazy == 0)return;
		crr->val = r - l + 1;
		crr->left->lazy = crr->right->lazy = 1;
		crr->lazy = 0;
	}
	void pull(node* crr){
		if(crr->left == nullptr)return;
		crr->val = crr->left->val + crr->right->val;
	}
	void update(node* crr, int l, int r, int lx, int rx){
		extend(crr);propogate(crr, lx, rx);
		if(rx < l or r < lx)return;
		if(l <= lx and rx <= r){
			crr->lazy = 1;propogate(crr, lx, rx);return;
		}
		int mid = lx + (rx - lx) / 2;
		update(crr->left, l, r, lx, mid);
		update(crr->right, l, r, mid + 1, rx);
		pull(crr);
	}
	int query(node* crr, int l, int r, int lx, int rx){
		extend(crr);propogate(crr, lx, rx);
		if(rx < l or lx > r)return 0;
		if(l <= lx and rx <= r)return crr->val;
		int mid = lx + (rx - lx) / 2;
		return query(crr->left, l, r, lx, mid) + query(crr->right, l, r, mid + 1, rx);
	}
};

int M;

int main(){
	setIO();
	cin >> M;
	Segtree sg;
	int prev = 0;
	while(M --){
		int t;
		cin >> t;
		if(t == 1){
			int x, y;
			cin >> x >> y;
			x += prev, y += prev;
			cout << (prev = sg.query(sg.root, x, y, 1, MX)) << '\n';
		} else {
			int x, y;
			cin >> x >> y;
			x += prev, y += prev;
			sg.update(sg.root, x, y, 1, MX);
		}
	}
	return 0;
}

Compilation message

apple.cpp: In function 'void setIO(std::string)':
apple.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   20 |   freopen((s + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   21 |   freopen((s + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	20 ms	6380 KB	Output is correct
5	Correct	27 ms	7788 KB	Output is correct
6	Correct	24 ms	7532 KB	Output is correct
7	Correct	25 ms	7788 KB	Output is correct
8	Correct	221 ms	58220 KB	Output is correct
9	Correct	419 ms	100716 KB	Output is correct
10	Correct	432 ms	111340 KB	Output is correct
11	Correct	448 ms	119788 KB	Output is correct
12	Correct	457 ms	123372 KB	Output is correct
13	Correct	412 ms	143768 KB	Output is correct
14	Correct	431 ms	145144 KB	Output is correct
15	Runtime error	695 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-