#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O1, O2, O3, Ofast")
#pragma GCC optimization ("trapv")
#pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max_heap priority_queue<ll>
#define min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> // size(), push(), top(), pop();
//#define min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout);
#define endl '\n'
#define md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;
ll const maxn = 2e5 + 10;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 998244353; //1e9 + 9, // 1e9 + 7;
ll const sq = 750;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}
ll q;
vector <pair <ll, ll>> child;
vector <ll> op, arr;
void breed(ll x, ll lx, ll rx){
if ((child[x].first != 0) || (rx - lx == 1))
return;
child[x].first = child.size();
child.push_back({0, 0});
op.push_back(-1);
arr.push_back(0);
child[x].second = child.size();
child.push_back({0, 0});
op.push_back(-1);
arr.push_back(0);
}
void propogate(ll x, ll lx, ll rx){
breed(x, lx, rx);
if (rx - lx == 1)
return;
if (op[x] == -1)
return;
ll a = child[x].first, b = child[x].second, mid = (lx + rx) / 2;
arr[a] = (mid - lx) * op[x];
arr[b] = (rx - mid) * op[x];
op[a] = op[x];
op[b] = op[x];
op[x] = -1;
}
ll get(ll l, ll r, ll x, ll lx, ll rx){
propogate(x, lx, rx);
if (l >= rx || lx >= r)
return 0;
if (l <= lx && rx <= r)
return arr[x];
ll a = child[x].first, b = child[x].second, mid = (lx + rx) / 2;
return get(l, r, a, lx, mid) + get(l, r, b, mid, rx);
}
void setter(ll l, ll r, ll val, ll x, ll lx, ll rx){
propogate(x, lx, rx);
if (l >= rx || lx >= r)
return;
if (l <= lx && rx <= r){
arr[x] = (rx - lx) * val;
op[x] = val;
return;
}
ll a = child[x].first, b = child[x].second, mid = (lx + rx) / 2;
setter(l, r, val, a, lx, mid);
setter(l, r, val, b, mid, rx);
arr[x] = arr[a] + arr[b];
}
int main(){
sariE;// filE;
child.push_back({0, 0});
arr.push_back(0);
op.push_back(-1);
ll enc = 0;
cin >> q;
while (q--){
ll chi, l, r; cin >> chi >> l >> r;
l += enc;
r += enc;
if (chi == 1){
ll ans = get(l, r + 1, 0, 0, 1e9 + 10);
cout << ans << endl;
enc = ans;
}
else{
setter(l, r + 1, 1, 0, 0, 1e9 + 10);
}
}
}
Compilation message
apple.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization ("unroll-loops")
|
apple.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O1, O2, O3, Ofast")
|
apple.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization ("trapv")
|
apple.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
16 ms |
8260 KB |
Output is correct |
| 5 |
Correct |
19 ms |
9160 KB |
Output is correct |
| 6 |
Correct |
19 ms |
8896 KB |
Output is correct |
| 7 |
Correct |
18 ms |
8900 KB |
Output is correct |
| 8 |
Correct |
196 ms |
74392 KB |
Output is correct |
| 9 |
Correct |
327 ms |
122480 KB |
Output is correct |
| 10 |
Correct |
323 ms |
130356 KB |
Output is correct |
| 11 |
Correct |
330 ms |
136560 KB |
Output is correct |
| 12 |
Correct |
341 ms |
139308 KB |
Output is correct |
| 13 |
Correct |
386 ms |
221736 KB |
Output is correct |
| 14 |
Correct |
396 ms |
221732 KB |
Output is correct |
| 15 |
Correct |
575 ms |
254908 KB |
Output is correct |
| 16 |
Correct |
541 ms |
256700 KB |
Output is correct |
| 17 |
Correct |
337 ms |
221744 KB |
Output is correct |
| 18 |
Correct |
371 ms |
221756 KB |
Output is correct |
| 19 |
Correct |
456 ms |
262144 KB |
Output is correct |
| 20 |
Correct |
459 ms |
262144 KB |
Output is correct |
