#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
struct node{
ll lb, rb; ll data = 0, lazy = 0;
node *l = nullptr, *r = nullptr;
node(ll lb0, ll rb0) {
lb = lb0, rb = rb0;
}
void extend() {
if(l == nullptr && lb < rb) {
ll md = (lb + rb) / 2;
l = new node(lb, md);
r = new node(md + 1, rb);
}
}
};
void prop(node* root) {
if((root -> lb) == (root -> rb) || root -> lazy == 0) return;
root -> extend();
(root -> l) -> lazy = root -> lazy;
(root -> r) -> lazy = root -> lazy;
ll md = ((root -> lb) + (root -> rb)) / 2;
ll a = md - (root -> lb) + 1, b = (root -> rb) - md;
(root -> l) -> data = a;
(root -> r) -> data = b;
root -> lazy = 0;
}
void update(node* root, ll lo, ll hi, ll val) {
prop(root);
if(root -> lb > hi || root -> rb < lo) return;
if(root -> lb >= lo && root -> rb <= hi) {
root -> data = val * ((root -> rb) - (root -> lb) + 1); root -> lazy = val;
prop(root); return;
}
root -> extend();
update(root -> l, lo, hi, val);
update(root -> r, lo, hi, val);
root -> data = (root -> l) -> data + (root -> r) -> data;
}
ll query(node* root, ll lo, ll hi) {
prop(root);
if(root -> lb > hi || root -> rb < lo) return 0;
if(root -> lb >= lo && root -> rb <= hi) return root -> data;
root -> extend();
return query(root -> l, lo, hi) + query(root -> r, lo, hi);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll q, c = 0; cin >> q; node* root = new node(0, 1000000000);
while(q--) {
ll d, lo, hi; cin >> lo >> hi; lo += c; hi += c;
if(d == 1) {
c = query(root, lo, hi);
cout << c << "\n";
}
else update(root, lo, hi, 1);
}
}
Compilation message
apple.cpp: In function 'int32_t main()':
apple.cpp:68:17: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
68 | if(d == 1) {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
