#include <bits/stdc++.h>
using namespace std;
long double PI = acos(-1);
long double DEL = 1e-12;
long long M = 1e9 + 7;
const long long N = 3e5 + 10;
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#define ftt cin>>tc;for(int cas=1;cas<=tc;++cas)
#define all(a) a.begin(),a.end()
#define sq(a) ((a)*(a))
#define double long double
#define dbg cout<<"\nhi\n";
#define int long long
#define nl cout<<"\n"
#define sp <<" "<<
#define mid ((l+r)>>1)
#define X real()
#define Y imag()
//*********************************** CHECK CONSTRAINTS ***********************************
int cnt, sum, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z, tc;
string s;
//************************************* CODE STARTS ****************************************
struct node{
int lson,rson,s,lz;
node():lson(-1),rson(-1),lz(0),s(0){}
};
vector<node> seg;
void push(int i,int l,int r){
if(seg[i].lz == 0){
return;
}
seg[i].s = r - l + 1;
seg[i].lz = 0;
if(l != r){
if(seg[i].lson == -1){
seg[i].lson = seg.size();
seg.emplace_back();
seg[seg[i].lson].lz = 1;
seg[seg[i].lson].s = mid - l + 1;
}
if(seg[i].rson == -1){
seg[i].rson = seg.size();
seg.emplace_back();
seg[seg[i].rson].lz = 1;
seg[seg[i].rson].s = r - mid;
}
}
// cout<<"_______" sp i sp l sp r;nl;
}
int query(int i,int l,int r,int a,int b){
push(i,l,r);
if(l > b or r < a or seg[i].s == 0){
return 0;
}
if(a <= l and r <= b){
return seg[i].s;
}
if(seg[i].lson == -1){
return 0;
}
return query(seg[i].lson,l,mid,a,b) + query(seg[i].rson,mid+1,r,a,b);
}
void update(int i,int l,int r,int a,int b){
push(i,l,r);
if(l > b or r < a){
return;
}
if(a <= l and r <= b){
seg[i].lz = 1;
push(i,l,r);
return;
}
if(seg[i].lson == -1){
seg[i].lson = seg.size();
seg.emplace_back();
}
if(seg[i].rson == -1){
seg[i].rson = seg.size();
seg.emplace_back();
}
update(seg[i].lson,l,mid,a,b);
update(seg[i].rson,mid+1,r,a,b);
seg[i].s = seg[seg[i].lson].s + seg[seg[i].rson].s;
// cout<<i sp l sp r sp seg[i].s sp seg[seg[i].lson].s sp seg[seg[i].rson].s sp seg[i].rson;nl;
}
int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
seg.emplace_back();
seg.emplace_back();
int c = 0;
ftt{
cin>>t>>l>>r;
if(t == 2){
update(1,1,1e9,l+c,r+c);
}
else{
c = query(1,1,1e9,l+c,r+c);
cout<<c;nl;
}
}
}
Compilation message
apple.cpp: In constructor 'node::node()':
apple.cpp:35:25: warning: 'node::lz' will be initialized after [-Wreorder]
35 | int lson,rson,s,lz;
| ^~
apple.cpp:35:23: warning: 'long long int node::s' [-Wreorder]
35 | int lson,rson,s,lz;
| ^
apple.cpp:36:9: warning: when initialized here [-Wreorder]
36 | node():lson(-1),rson(-1),lz(0),s(0){}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
