Submission #1244448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244448		SmuggingSpun	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	28 ms	840 KiB

apple

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
struct Data{
	int lc, rc, sum;
	Data(){}
	Data(int _lc, int _rc, int _sum) : lc(_lc), rc(_rc), sum(_sum) {}
};
vector<Data>st(1, Data(-1, -1, int(1e9)));
int get(int u, int v, int id = 0, int l = 1, int r = int(1e9)){
	if(l > v || r < u || (id != -1 && st[id].sum == 0)){
		return 0;
	}
	if(id == -1){
		return min(r, v) - max(l, u) + 1;
	}
	if(u <= l && v >= r){
		return st[id].sum;
	}
	int m = (l + r) >> 1;
	return get(u, v, st[id].lc, l, m) + get(u, v, st[id].rc, m + 1, r);
}
void update(int u, int v, int id = 0, int l = 1, int r = int(1e9)){
	if(l > v || r < u || st[id].sum == 0){
		return;
	}
	if(u <= l && v >= r){
		st[id].sum = 0;
		return;
	}
	int m = (l + r) >> 1;
	if(st[id].lc == -1){
		st[id].lc = st.size();
		st.emplace_back(Data(-1, -1, m - l + 1));
	}
	if(st[id].rc == -1){
		st[id].rc = st.size();
		st.emplace_back(Data(-1, -1, r - m));
	}
	update(u, v, st[id].lc, l, m);
	update(u, v, st[id].rc, m + 1, r);
	st[id].sum = st[st[id].lc].sum + st[st[id].rc].sum;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int m;
	cin >> m;
	for(int _ = 0, c = 0; _ < m; _++){
		int d, x, y;
		cin >> d >> x >> y;
		if(d == 1){
			cout << (c = y - x + 1 - get(x + c, y + c)) << "\n";
		}
		else{
			update(x + c, y + c);
		}
	}
}

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:47:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100