#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e5 + 5;
ll L[N * 60], R[N * 60], st[N * 60], lazy[N * 60], ptr = 2;
void push(ll v, ll l, ll r)
{
if (!lazy[v])
return;
lazy[v] = 0;
ll mid = (l + r) >> 1;
if (L[v] == -1)
L[v] = ptr++;
if (R[v] == -1)
R[v] = ptr++;
st[L[v]] = mid - l + 1, lazy[L[v]] = 1;
st[R[v]] = r - mid, lazy[R[v]] = 1;
}
ll query(ll i, ll j, ll l, ll r, ll v)
{
if (v == -1)
return 0;
if (i <= l and r <= j)
return st[v];
ll mid = (l + r) >> 1;
push(v, l, r);
if (j <= mid)
return query(i, j, l, mid, L[v]);
if (i > mid)
return query(i, j, mid + 1, r, R[v]);
return query(i, j, l, mid, L[v]) + query(i, j, mid + 1, r, R[v]);
}
ll modify(ll i, ll j, ll l, ll r, ll v)
{
if (v == -1)
v = ptr++;
if (max(i, l) > min(j, r))
return v;
if (i <= l and r <= j)
{
st[v] = r - l + 1;
lazy[v] = 1;
return v;
}
push(v, l, r);
ll mid = (l + r) >> 1;
L[v] = modify(i, j, l, mid, L[v]);
R[v] = modify(i, j, mid + 1, r, R[v]);
st[v] = st[L[v]] + st[R[v]];
return v;
}
void solve()
{
ll q;
cin >> q;
for (ll i = 1; i < 60 * N; i++)
L[i] = R[i] = -1;
ll c = 0;
while (q--)
{
ll t, l, r;
cin >> t >> l >> r;
l += c, r += c;
if (t == 2)
modify(l, r, 1, 1e9, 1);
else
cout << (c = query(l, r, 1, 1e9, 1)) << endl;
}
}
/*
*/
int main()
{
ANDROID
// precomp();
ll t = 1;
// cin >> t;
for (ll i = 1; i <= t; i++)
// cout << "Case #" << i << ": ",
solve();
cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
97624 KB |
Output is correct |
| 2 |
Correct |
16 ms |
97628 KB |
Output is correct |
| 3 |
Correct |
16 ms |
97624 KB |
Output is correct |
| 4 |
Correct |
22 ms |
101968 KB |
Output is correct |
| 5 |
Correct |
24 ms |
101976 KB |
Output is correct |
| 6 |
Correct |
25 ms |
101976 KB |
Output is correct |
| 7 |
Correct |
24 ms |
101980 KB |
Output is correct |
| 8 |
Correct |
83 ms |
114548 KB |
Output is correct |
| 9 |
Correct |
165 ms |
122960 KB |
Output is correct |
| 10 |
Correct |
177 ms |
127056 KB |
Output is correct |
| 11 |
Correct |
191 ms |
131408 KB |
Output is correct |
| 12 |
Correct |
190 ms |
131156 KB |
Output is correct |
| 13 |
Correct |
148 ms |
135248 KB |
Output is correct |
| 14 |
Correct |
156 ms |
135608 KB |
Output is correct |
| 15 |
Correct |
228 ms |
165980 KB |
Output is correct |
| 16 |
Correct |
243 ms |
168584 KB |
Output is correct |
| 17 |
Correct |
148 ms |
137296 KB |
Output is correct |
| 18 |
Correct |
147 ms |
137300 KB |
Output is correct |
| 19 |
Correct |
228 ms |
168272 KB |
Output is correct |
| 20 |
Correct |
230 ms |
168276 KB |
Output is correct |
