#include <bits/stdc++.h>
#define el "\n"
#define fu(i, a, b) for (long long i = a; i <= b; ++i)
#define fd(i, a, b) for (long long i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r) (rng);
}
ll last(ll msk) {return msk & (-msk);}
ll pop_cnt(ll msk) {return __builtin_popcountll(msk);}
ll ctz(ll msk) {return __builtin_ctzll(msk);}
ll lg(ll msk) {return 63 - __builtin_clzll(msk);}
template<class T1, class T2> bool minimize(T1 &a, T2 b) {
return a > b ? a = b, 1 : 0;
}
template<class T1, class T2> bool maximize(T1 &a, T2 b) {
return a < b ? a = b, 1 : 0;
}
template<class T> void print(T a) {
for (auto x : a) cout << x << " ";
cout << el;
}
template<class T> void compress(T &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
const long long N = 3e6 + 27, inf = 2e18, bl = 320, base = 311, mod = 1e9 + 7, lim = 30;
int q, cur;
struct SegmentTree {
int n, l, r;
vector<int> t, le, ri, lazy;
SegmentTree(int _n, int _l, int _r) {
l = _l, r = _r;
n = _n;
int len = n * lg((r - l + 2));
t.resize(len, 0);
le.resize(len, 0);
ri.resize(len, 0);
lazy.resize(len, 0);
}
int cur = 1;
void addNode(int &x) {
if (x) return;
x = ++cur;
}
void down(int id, int l, int r) {
// cout << le[id] << ' ' << ri[id] << el;
addNode(le[id]);
addNode(ri[id]);
if (!lazy[id]) return;
int mid = (l + r) / 2;
t[le[id]] = mid - l + 1;
t[ri[id]] = r - mid;
lazy[le[id]] = lazy[ri[id]] = 1;
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v) {
// cout << id << ' ' << l << ' ' << r << el;
if (r < u || l > v) return;
if (u <= l && r <= v) {
t[id] = r - l + 1;
lazy[id] = 1;
return;
}
down(id, l, r);
int mid = (l + r) / 2;
update(le[id], l, mid, u, v);
update(ri[id], mid + 1, r, u, v);
t[id] = t[le[id]] + t[ri[id]];
}
int get(int id, int l, int r, int u, int v) {
// cout << id << ' ' << l << ' ' << r << el;
if (!id || r < u || l > v) return 0;
if (u <= l && r <= v) return t[id];
down(id, l, r);
int mid = (l + r) / 2;
int t1 = get(le[id], l, mid, u, v);
int t2 = get(ri[id], mid + 1, r, u, v);
return t1 + t2;
}
int get(int u, int v) {
return get(1, l, r, u, v);
}
void update(int u, int v) {
return update(1, l, r, u, v);
}
};
signed main() {
// freopen("fence.inp", "r", stdin);
// freopen("fence.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> q;
SegmentTree seg(q, 1, 1e9);
// seg.update(1, 2);
// cout << seg.cur;
while (q--) {
int type, l, r;
cin >> type >> l >> r;
l += cur;
r += cur;
if (type & 1) {
cur = seg.get(l, r);
cout << cur << el;
}
else seg.update(l, r);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
504 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4176 KB |
Output is correct |
| 5 |
Correct |
11 ms |
5200 KB |
Output is correct |
| 6 |
Correct |
11 ms |
5212 KB |
Output is correct |
| 7 |
Correct |
11 ms |
5140 KB |
Output is correct |
| 8 |
Correct |
66 ms |
24136 KB |
Output is correct |
| 9 |
Correct |
138 ms |
47944 KB |
Output is correct |
| 10 |
Correct |
156 ms |
47688 KB |
Output is correct |
| 11 |
Correct |
180 ms |
47988 KB |
Output is correct |
| 12 |
Correct |
170 ms |
47944 KB |
Output is correct |
| 13 |
Correct |
139 ms |
48368 KB |
Output is correct |
| 14 |
Correct |
145 ms |
48200 KB |
Output is correct |
| 15 |
Runtime error |
199 ms |
94536 KB |
Execution killed with signal 11 |
| 16 |
Halted |
0 ms |
0 KB |
- |
