#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9+7;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
int cnt=0;
struct Node{
int sum, lazy, left, right, tl, tr;
Node(): sum(0), lazy(0), left(-1), right(-1) {}
};
Node segtree[nax*64];
void expand(int pos){
if(segtree[pos].lazy==1){
segtree[pos].sum=segtree[pos].tr-segtree[pos].tl+1;
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
if(segtree[pos].left==-1){
segtree[pos].left=++cnt;
segtree[segtree[pos].left].tl=segtree[pos].tl;
segtree[segtree[pos].left].tr=mid;
}
if(segtree[pos].right==-1){
segtree[pos].right=++cnt;
segtree[segtree[pos].right].tl=mid+1;
segtree[segtree[pos].right].tr=segtree[pos].tr;
}
segtree[segtree[pos].left].lazy=segtree[segtree[pos].right].lazy=1;
}
segtree[pos].lazy=0;
}
void update(int pos,int l,int r){
expand(pos);
//cout<<pos<<" "<<segtree[pos].tl<<" "<<segtree[pos].tr<<endl;
if(segtree[pos].tl==l&&segtree[pos].tr==r){
segtree[pos].lazy=1;
expand(pos);
return;
}
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
if(segtree[pos].left==-1){
segtree[pos].left=++cnt;
segtree[segtree[pos].left].tl=segtree[pos].tl;
segtree[segtree[pos].left].tr=mid;
}
if(segtree[pos].right==-1){
segtree[pos].right=++cnt;
segtree[segtree[pos].right].tl=mid+1;
segtree[segtree[pos].right].tr=segtree[pos].tr;
}
if(l>mid) update(segtree[pos].right,l,r);
else if (r<=mid) update(segtree[pos].left,l,r);
else{
update(segtree[pos].left,l,mid);
update(segtree[pos].right,mid+1,r);
}
expand(segtree[pos].left);
expand(segtree[pos].right);
segtree[pos].sum=segtree[segtree[pos].left].sum+segtree[segtree[pos].right].sum;
return;
}
int query(int pos,int l,int r){
expand(pos);
if(segtree[pos].tl==l&&segtree[pos].tr==r){
return segtree[pos].sum;
}
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
if(segtree[pos].left==-1){
segtree[pos].left=++cnt;
segtree[segtree[pos].left].tl=segtree[pos].tl;
segtree[segtree[pos].left].tr=mid;
}
if(segtree[pos].right==-1){
segtree[pos].right=++cnt;
segtree[segtree[pos].right].tl=mid+1;
segtree[segtree[pos].right].tr=segtree[pos].tr;
}
if(l>mid) return query(segtree[pos].right,l,r);
else if (r<=mid) return query(segtree[pos].left,l,r);
else{
return query(segtree[pos].left,l,mid)+query(segtree[pos].right,mid+1,r);
}
}
int main(){
optimise;
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
//setIO("snowcow");
int n;
cin>>n;
int lst=0;
segtree[0].sum=0;
segtree[0].lazy=0;
segtree[0].tl=0;
segtree[0].tr=1e9;
for (int i = 0; i < n; ++i)
{
int c;
cin>>c;
if(c==1){
int l,r;
cin>>l>>r;
l+=lst;
r+=lst;
lst=query(0,l,r);
cout <<lst<<endl;
}else{
int l,r;
cin>>l>>r;
l+=lst;
r+=lst;
update(0,l,r);
}
}
return 0;
}
Compilation message
apple.cpp: In function 'void setIO(std::string)':
apple.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
150620 KB |
Output is correct |
| 2 |
Correct |
25 ms |
150668 KB |
Output is correct |
| 3 |
Correct |
25 ms |
150612 KB |
Output is correct |
| 4 |
Correct |
37 ms |
150620 KB |
Output is correct |
| 5 |
Correct |
41 ms |
150764 KB |
Output is correct |
| 6 |
Correct |
45 ms |
151064 KB |
Output is correct |
| 7 |
Correct |
40 ms |
150616 KB |
Output is correct |
| 8 |
Correct |
121 ms |
150848 KB |
Output is correct |
| 9 |
Correct |
239 ms |
151088 KB |
Output is correct |
| 10 |
Correct |
252 ms |
151312 KB |
Output is correct |
| 11 |
Correct |
247 ms |
151124 KB |
Output is correct |
| 12 |
Correct |
257 ms |
151124 KB |
Output is correct |
| 13 |
Correct |
236 ms |
151124 KB |
Output is correct |
| 14 |
Correct |
227 ms |
151168 KB |
Output is correct |
| 15 |
Execution timed out |
2051 ms |
151128 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
