#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
using namespace __gnu_pbds;
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
const int kax = 25+5;
#include<bits/stdc++.h>
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> struct node
{
T val = 0; T lazy = 0; node<T>* c[2];
node() {c[0] = c[1] = NULL; }
void push_lazy(int l, int r){
if(lazy){
int md = (l+r)/2;
if(!c[0]) c[0] = new node();
c[0]->val = (md-l+1);
if(!c[1]) c[1] = new node();
c[1]->val = (r-md);
c[0]->lazy = c[1]->lazy = 1;
lazy = 0;
}
}
void update(int l, int r, int i, int j){
if(r < i || l > j) return;
if(i <= l && r <= j){ val = (r-l+1); lazy = 1; return; }
push_lazy(l,r);
int md = (l+r)/2;
if(i <= md){
if(!c[0]) c[0] = new node();
c[0]->update(l,md,i,j);
}
if(j > md){
if(!c[1]) c[1] = new node();
c[1]->update(md+1,r,i,j);
}
val = 0;
for(int i = 0; i < 2; i++) if(c[i]) val += c[i]->val;
//cout << l << ' ' << r << " " << val << endl;
}
T query(int l, int r, int i, int j) {
if(r < i || l > j) return 0;
if(i <= l && r <= j) return val;
push_lazy(l,r);
int md = (l+r)/2; T res = 0;
if(c[0]) res += c[0]->query(l,md,i,j);
if(c[1]) res += c[1]->query(md+1,r,i,j);
return res;
}
};
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int m;
cin >> m;
int c = 0;
node<int> rt = node<int>();
for (int i = 0; i < m; ++i)
{
int d, x, y;
cin >> d >> x >> y;
x--,y--;
if(d == 1){
int ans = rt.query(0,INF, x+c, y+c);
cout << ans << endl;
c += ans;
} else {
//cout << x+c << " " << y+c << endl;
rt.update(0,INF,x+c, y+c);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
