using namespace std;
#include <bits/stdc++.h>
#define i64 long long
#define u32 unsigned int
#define u64 unsigned long long
#define f32 float
#define f64 double
#define vec vector
#define F0R(i, e) for(i64 i = 0; i<e; i++)
#define FOR(i, s, e) for(i64 i = s; i<e; i++)
#define F0Rd(i, e) for(i64 i = e-1; i>=0; i--)
#define FORd(i, s, e) for(i64 i = e-1; i>=s; i--)
#define TRAV(v, g) for(auto v: g)
const i64 INF_32 = INT32_MAX/3;
const i64 INF_64 = INT64_MAX/3;
struct SegNode {
i64 ll=0, rr=((i64)1<<32);
i64 cnt = 0;
SegNode *left=nullptr, *right=nullptr;
i64 update(i64 l, i64 r) {
if(ll >= r || rr <= l || cnt == rr-ll) {
return 0;
}
if(l<=ll && r>=rr) {
i64 dif = (rr-ll)-cnt;
cnt = rr-ll;
return dif;
}
if(left == nullptr) {
assert(right == nullptr);
i64 m = (ll+rr)/2;
left = new SegNode {ll, m};
right = new SegNode {m, rr};
}
i64 dl = left->update(l, r);
i64 dr = right->update(l, r);
// cout << "retrieved dif " << dl+dr << endl;
cnt += dl + dr;
return dl+dr;
}
i64 query(i64 l, i64 r) {
// cerr << "querying... " << l << " " << r << endl;
if(ll>=r || rr <= l) {
return 0;
}
if(l<=ll && r>=rr) {
return cnt;
}
if(rr-ll == cnt) {
i64 al = max(ll, l);
i64 br = min(rr, r);
return br-al;
}
if(left != nullptr) {
assert(right != nullptr);
i64 ccnt = left->query(l, r) + right->query(l, r);
// cout << "retrieved cnt " << ccnt << endl;
return ccnt;
}
return 0;
}
};
SegNode root;
void solve() {
i64 m;
cin >> m;
i64 c = 0;
while(m--) {
i64 d,x,y; cin >> d >> x >> y; x--;
x+=c;
y+=c;
if(d==1) {
i64 res = root.query(x, y);
c += res;
cout << res << '\n';
}
else {
root.update(x, y);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
i64 t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
