Submission #890262

# Submission time Handle Problem Language Result Execution time Memory
890262 2023-12-20T21:20:16 Z Justin1 Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
383 ms 262144 KB
#include <bits/stdc++.h>
#define f first
#define s second
// #define int long long
using namespace std;
 
class dynamicSeg { //range max query, range set update
	int lzy, val;
	int l, r;
	dynamicSeg *L = NULL, *R = NULL;
	void extend(dynamicSeg *&node, int l, int r) {
		if (node == NULL) node = new dynamicSeg(l, r);
	}
	void push() {
		if (!lzy) return;
		int mid = (this->l + this->r) / 2;
		extend(L, this->l, mid), extend(R, mid + 1, this->r);
		L-> val = L->r - L->l + 1;
		R-> val = R->r - R->l + 1;
		L-> lzy = R->lzy = !(lzy = 0);
	}
public:
	dynamicSeg (int sz) : l(1), r(sz) {}
	dynamicSeg (int l, int r) : l(l), r(r) {}
	void upd(int l, int r) {
		push();
		if (this->r < l || r < this->l) return;
		if (l <= this->l && this->r <= r) {
			val = this->r - this->l + 1;
			lzy = 1;
			return;
		}
		int mid = (this->l + this->r) / 2;
		extend(L, this->l, mid), extend(R, mid + 1, this->r);
		L->upd(l, r), R->upd(l, r);
		val = L->val + R->val;
	}
	int qry(int l, int r) {
		push();
		if (this->r < l || r < this->l) return 0;
		if (l <= this->l && this->r <= r) return val;
		int mid = (this->l + this->r) / 2;
		return (L ? L->qry(l, r) : 0) + (R ? R->qry(l, r) : 0);
	}
};
 
int n, m, k, x, y, z;
dynamicSeg seg(1'000'000'000);
 
void solve() {
	int C = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x >> y >> z;
		if (x == 1) cout << (C = seg.qry(y + C, z + C)) << "\n"; 
		else seg.upd(y + C, z + C);
	}
}
 
signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    cout << fixed << setprecision(10);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

Compilation message

apple.cpp: In member function 'int dynamicSeg::qry(int, int)':
apple.cpp:42:7: warning: unused variable 'mid' [-Wunused-variable]
   42 |   int mid = (this->l + this->r) / 2;
      |       ^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 14 ms 9420 KB Output is correct
5 Correct 17 ms 11356 KB Output is correct
6 Correct 17 ms 11096 KB Output is correct
7 Correct 18 ms 11356 KB Output is correct
8 Correct 144 ms 86868 KB Output is correct
9 Correct 309 ms 150532 KB Output is correct
10 Correct 324 ms 166728 KB Output is correct
11 Correct 345 ms 179204 KB Output is correct
12 Correct 331 ms 184916 KB Output is correct
13 Correct 309 ms 215096 KB Output is correct
14 Correct 299 ms 217280 KB Output is correct
15 Runtime error 383 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -