#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
using namespace std;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct SegTree{
struct Node{
int val, lnode, rnode;
bool lazy;
Node():lnode(-1),rnode(-1),val(0),lazy(0){}
};
Node segtree[10000000];
int ind = 1;
SegTree(){
segtree[0].val=0;
segtree[0].lazy=0;
}
void lyap(int node, int tarl, int tarr){
int mid = tarl+(tarr-tarl)/2;
if (segtree[node].lnode==-1){
segtree[node].lnode=ind++;
}
}
void ryap(int node, int tarl, int tarr){
int mid = tarl+(tarr-tarl)/2;
if (segtree[node].rnode==-1){
segtree[node].rnode=ind++;
}
}
void dallan(int node, int tarl, int tarr){
if (segtree[node].lazy==1){
lyap(node, tarl, tarr);
ryap(node, tarl, tarr);
segtree[segtree[node].lnode].lazy=1;
segtree[segtree[node].rnode].lazy=1;
segtree[node].val=tarr-tarl+1;
}
segtree[node].lazy=0;
}
int query(int l, int r, int tarl = 1, int tarr = 1000000000, int node = 0){
dallan(node, tarl, tarr);
if (tarl>=l && tarr<=r) return segtree[node].val;
if (tarl>r || tarr<l) return 0ll;
int rval = 0;
int mid = tarl+(tarr-tarl)/2;
if (segtree[node].lnode!=-1){
rval+=query(l, r, tarl, mid, segtree[node].lnode);
}
if (segtree[node].rnode!=-1){
rval+=query(l, r, mid+1, tarr, segtree[node].rnode);
}
return rval;
}
void update(int l, int r, int tarl = 1, int tarr = 1000000000, int node = 0) {
dallan(node, tarl, tarr);
if (tarl>=l && tarr<=r){
segtree[node].lazy=1;
dallan(node, tarl, tarr);
return;
}
if (tarl>r || tarr<l) return;
int mid = tarl+(tarr-tarl)/2;
if (mid>=l){
lyap(node, tarl, tarr);
update(l, r, tarl, mid, segtree[node].lnode);
}
if (mid+1<=r){
ryap(node, tarl, tarr);
update(l, r, mid+1, tarr, segtree[node].rnode);
}
segtree[node].val=0ll;
if (segtree[node].lnode!=-1){
dallan(segtree[node].lnode, tarl, mid);
segtree[node].val+=segtree[segtree[node].lnode].val;
}
if (segtree[node].rnode!=-1){
dallan(segtree[node].rnode, mid+1, tarr);
segtree[node].val+=segtree[segtree[node].rnode].val;
}
}
};
int32_t main(){
ios;
int t=1;
int tno = 0;
if (!t) cin>>t;
while (t-(tno++)){
SegTree segtree;
deci(q);
int c = 0;
while (q--){
deci(d);
deci(l);deci(r);
l+=c;
r+=c;
if (d==1){
c=segtree.query(l,r);
cout<<c<<endl;
}
else {
segtree.update(l,r);
}
}
}
}
Compilation message
apple.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize("Bismillahirrahmanirrahim")
|
apple.cpp: In constructor 'SegTree::Node::Node()':
apple.cpp:31:19: warning: 'SegTree::Node::rnode' will be initialized after [-Wreorder]
31 | int val, lnode, rnode;
| ^~~~~
apple.cpp:31:7: warning: 'int SegTree::Node::val' [-Wreorder]
31 | int val, lnode, rnode;
| ^~~
apple.cpp:33:3: warning: when initialized here [-Wreorder]
33 | Node():lnode(-1),rnode(-1),val(0),lazy(0){}
| ^~~~
apple.cpp: In member function 'void SegTree::lyap(int, int, int)':
apple.cpp:42:7: warning: unused variable 'mid' [-Wunused-variable]
42 | int mid = tarl+(tarr-tarl)/2;
| ^~~
apple.cpp: In member function 'void SegTree::ryap(int, int, int)':
apple.cpp:48:7: warning: unused variable 'mid' [-Wunused-variable]
48 | int mid = tarl+(tarr-tarl)/2;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
156804 KB |
Output is correct |
| 2 |
Correct |
80 ms |
156856 KB |
Output is correct |
| 3 |
Correct |
87 ms |
156748 KB |
Output is correct |
| 4 |
Correct |
90 ms |
156872 KB |
Output is correct |
| 5 |
Correct |
90 ms |
156864 KB |
Output is correct |
| 6 |
Correct |
89 ms |
156804 KB |
Output is correct |
| 7 |
Correct |
90 ms |
156848 KB |
Output is correct |
| 8 |
Correct |
166 ms |
157048 KB |
Output is correct |
| 9 |
Correct |
278 ms |
157168 KB |
Output is correct |
| 10 |
Correct |
273 ms |
157332 KB |
Output is correct |
| 11 |
Correct |
269 ms |
157284 KB |
Output is correct |
| 12 |
Correct |
274 ms |
157248 KB |
Output is correct |
| 13 |
Correct |
252 ms |
157236 KB |
Output is correct |
| 14 |
Correct |
255 ms |
157232 KB |
Output is correct |
| 15 |
Correct |
320 ms |
158140 KB |
Output is correct |
| 16 |
Correct |
316 ms |
159396 KB |
Output is correct |
| 17 |
Correct |
256 ms |
159408 KB |
Output is correct |
| 18 |
Correct |
260 ms |
159312 KB |
Output is correct |
| 19 |
Correct |
322 ms |
159464 KB |
Output is correct |
| 20 |
Correct |
331 ms |
159612 KB |
Output is correct |
