Submission #331366

#TimeUsernameProblemLanguageResultExecution timeMemory
331366ronnithMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
704 ms262148 KiB
#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){}
	void extend(){
		if(left != nullptr)return;
		left = new node();
		right = new node();
	}
	void propogate(int l, int r){
		if(lazy == 0)return;
		val = r - l + 1;
		left->lazy = right->lazy = 1;
		lazy = 0;
	}
	void pull(){
		if(left == nullptr)return;
		val = left->val + right->val;
	}
};
struct Segtree{
	node* root;
	Segtree(){
		root = new node();
	}
	void update(node* crr, int l, int r, int lx, int rx){
		crr->extend();crr->propogate(lx, rx);
		if(rx < l or r < lx)return;
		if(l <= lx and rx <= r){
			crr->lazy = 1;crr->propogate(lx, rx);return;
		}
		int mid = lx + (rx - lx) / 2;
		update(crr->left, l, r, lx, mid);
		update(crr->right, l, r, mid + 1, rx);
		crr->pull();
	}
	int query(node* crr, int l, int r, int lx, int rx){
		crr->extend();crr->propogate(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 (stderr)

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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...