#include <bits/stdc++.h>
namespace newbiezah {
#ifdef LOCAL
#include "E:\cp-Library\debug.h"
#else
#define dbg(...)
#endif
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int((x).size()))
#define REV(x) reverse(ALL(x))
#define UNIQUE(x) sort(ALL(x)), x.erase(unique(ALL(x)), x.end())
#define mask(x) (1 << (x))
#define fi first
#define se second
#define ft front()
#define bk back()
#define ppb pop_back()
#define ppf pop_front()
#define pb push_back
#define pf push_front
#define eb emplace_back
#define mp make_pair
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define tcT template<class T
tcT> using V = std::vector<T>;
tcT> int ilb(V<T> &a, const T &b) { return int(lb(ALL(a), b) - a.begin()); }
tcT> int iub(V<T> &a, const T &b) { return int(ub(ALL(a), b) - a.begin()); }
tcT, size_t sz>
using AR = std::array<T, sz>;
using ll = int64_t;
using db = double;
using str = std::string;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using VI = V<int>;
using VL = V<ll>;
using VS = V<str>;
using VB = V<bool>;
using VPI = V<pi>;
using VPL = V<pl>;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
tcT> using pq = std::priority_queue<T>;
tcT> using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
tcT> bool ckmax(T &u, T v) { return v > u ? u = v, true : false; }
tcT> bool ckmin(T &u, T v) { return v < u ? u = v, true : false; }
#define FOR(i, a, n) for (int i = (a); i < (n); i++)
#define F0R(i, n) FOR(i, 0, n)
#define FORd(i, a, n) for (int i = (n) - 1; i >= (a); i--)
#define F0Rd(i, n) FORd(i, 0, n)
#define rep(n) F0R(_, n)
#define trav(a, v) for (auto &a : v)
#define each(a, b, v) for (auto &&[a, b] : v)
#define each3(a, b, c, v) for (auto &&[a, b, c] : v)
const char nl = '\n';
const int mod1 = int(1e9)+7, mod9 = 998244353;
const int dxi[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dyi[8] = {0, 1, 0, -1, 1, -1, 1, -1};
} // namespace newbiezah
using namespace newbiezah;
using namespace std;
const int sz = 1<<30;
tcT> struct node {
T val = 0, lz = 0; node<T>* c[2];
node() { F0R(i, 2) c[i] = NULL; }
void push(int l, int r) {
if (lz) {
val = r-l;
F0R(i, 2) {
if (!c[i]) c[i] = new node();
c[i]->lz = 1;
}
}
lz = 0;
}
void pull(int l, int r) {
val = 0;
int mi = (l+r)/2;
if (c[0]) { c[0]->push(l, mi); val += c[0]->val; }
if (c[1]) { c[1]->push(mi, r); val += c[1]->val; }
}
int qry(int ql, int qr, int l = 0, int r = sz) {
push(l, r);
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) {
return val;
}
assert(l < r);
int mi = (l + r) / 2;
T res = 0;
if (c[0]) res += c[0]->qry(ql, qr, l, mi);
if (c[1]) res += c[1]->qry(ql, qr, mi, r);
return res;
}
void upd(int ql, int qr, int l = 0, int r = sz) {
push(l, r);
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) {
lz = 1;
push(l, r); return;
}
assert(l < r);
int mi = (l + r) / 2;
if (ql < mi) {
if (!c[0]) c[0] = new node();
c[0]->upd(ql, qr, l, mi);
}
if (qr > mi) {
if (!c[1]) c[1] = new node();
c[1]->upd(ql, qr, mi, r);
}
pull(l, r);
}
};
node<int> rt;
int n, c;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
rep(n) {
int t, l, r; cin >> t >> l >> r;
l += c, r += c;
if (t == 1) {
c = rt.qry(l, r+1);
cout << c << nl;
} else {
rt.upd(l, r+1);
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
22 ms |
6536 KB |
Output is correct |
| 5 |
Correct |
24 ms |
8004 KB |
Output is correct |
| 6 |
Correct |
21 ms |
7660 KB |
Output is correct |
| 7 |
Correct |
20 ms |
7884 KB |
Output is correct |
| 8 |
Correct |
172 ms |
59896 KB |
Output is correct |
| 9 |
Correct |
332 ms |
101684 KB |
Output is correct |
| 10 |
Correct |
357 ms |
114636 KB |
Output is correct |
| 11 |
Correct |
366 ms |
123236 KB |
Output is correct |
| 12 |
Correct |
390 ms |
126960 KB |
Output is correct |
| 13 |
Correct |
323 ms |
146892 KB |
Output is correct |
| 14 |
Correct |
343 ms |
148300 KB |
Output is correct |
| 15 |
Runtime error |
550 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Halted |
0 ms |
0 KB |
- |
