Submission #887299

#TimeUsernameProblemLanguageResultExecution timeMemory
887299alex_2008Monkey and Apple-trees (IZhO12_apple)C++14
100 / 100
345 ms71764 KiB
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <bitset>
typedef long long ll;
using namespace std;
const int N = 1e7 + 10;
int sz = 1;
int lazy[N];
int sm[N];
int l[N];
int r[N];
void update(int v, int tl, int tr, int ql, int qr) {
	if (tl > qr || tr < ql) {
		return;
	}
	if (tl >= ql && tr <= qr) {
		sm[v] = (tr - tl + 1);
		lazy[v] = 1;
		return;
	}
	if (!l[v]) l[v] = ++sz;
	if (!r[v]) r[v] = ++sz;
	int tm = (tl + tr) / 2;
	if (lazy[v]) {
		lazy[l[v]] = 1;
		sm[l[v]] = (tm - tl + 1);
		lazy[r[v]] = 1;
		sm[r[v]] = (tr - tm);
		lazy[v] = 0;
	}
	update(l[v], tl, tm, ql, qr);
	update(r[v], tm + 1, tr, ql, qr);
	sm[v] = sm[l[v]] + sm[r[v]];
}
int sum(int v, int tl, int tr, int ql, int qr) {
	if (tr < ql || tl > qr) return 0;
	if (tl >= ql && tr <= qr) {
		return sm[v];
	}
	if (!l[v]) l[v] = ++sz;
	if (!r[v]) r[v] = ++sz;
	int tm = (tl + tr) / 2;
	if (lazy[v]) {
		lazy[l[v]] = 1;
		sm[l[v]] = (tm - tl + 1);
		lazy[r[v]] = 1;
		sm[r[v]] = (tr - tm);
		lazy[v] = 0;
	}
	return sum(l[v], tl, tm, ql, qr) + sum(r[v], tm + 1, tr, ql, qr);
}
int main() {
	int m, c = 0;
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 2) {
			update(1, 1, 1e9, x + c, y + c);
		}
		else {
			c = sum(1, 1, 1e9, x + c, y + c);
			cout << c << "\n";
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...