#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
const ll MAX_N = (1e9 + 5);
const ll MAX_CONST = (5e6);
template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}
auto start_time = chrono::high_resolution_clock().now();
auto end_time = chrono::high_resolution_clock().now();
ll m;
ll c;
ll last_node;
ll seg;
vector<ll> val;
vector<ll> left_node;
vector<ll> right_node;
vector<ll> lazy;
void st_time(){
start_time = chrono::high_resolution_clock().now();
}
void pr_time(){
end_time = chrono::high_resolution_clock().now();
cout << "time is " << chrono::duration_cast<chrono::microseconds>(end_time-start_time).count() << endl;
}
inline void extend(ll ind, ll l, ll r){
if(l == r){return;}
if(left_node[ind] == -1){
left_node[ind] = ++last_node;
}
if(right_node[ind] == -1){
right_node[ind] = ++last_node;
}
}
/*
void push_lazy(int node) {
if (segtree[node].lazy) {
segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
int mid = (segtree[node].tl + segtree[node].tr) / 2;
if (segtree[node].l == -1) {
segtree[node].l = cnt++;
segtree[segtree[node].l].tl = segtree[node].tl;
segtree[segtree[node].l].tr = mid;
}
if (segtree[node].r == -1) {
segtree[node].r = cnt++;
segtree[segtree[node].r].tl = mid + 1;
segtree[segtree[node].r].tr = segtree[node].tr;
}
segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
segtree[node].lazy = 0;
}
}
*/
inline void pushdownwards(ll ind, ll l, ll r){
if(lazy[ind] != 0){
val[ind] = r-l+1;
ll m = (l+r)/2;
if(left_node[ind] == -1){
left_node[ind] = ++last_node;
}
if(right_node[ind] == -1){
right_node[ind] = ++last_node;
}
lazy[left_node[ind]] = lazy[right_node[ind]] = 1;
lazy[ind] = 0;
}
}
/*
int query(int node, int l, int r) {
push_lazy(node);
if (l == segtree[node].tl && r == segtree[node].tr)
return segtree[node].sum;
else {
int mid = (segtree[node].tl + segtree[node].tr) / 2;
if (segtree[node].l == -1) {
segtree[node].l = cnt++;
segtree[segtree[node].l].tl = segtree[node].tl;
segtree[segtree[node].l].tr = mid;
}
if (segtree[node].r == -1) {
segtree[node].r = cnt++;
segtree[segtree[node].r].tl = mid + 1;
segtree[segtree[node].r].tr = segtree[node].tr;
}
if (l > mid) return query(segtree[node].r, l, r);
else if (r <= mid) return query(segtree[node].l, l, r);
else
return query(segtree[node].l, l, mid) +
query(segtree[node].r, mid + 1, r);
}
}
*/
inline ll get_val(ll ind, ll tl, ll tr, ll l, ll r){
pushdownwards(ind, l, r);
if(tl == l && tr == r){
return val[ind];
}else{
ll m = (l+r)/2;
if(left_node[ind] == -1){
left_node[ind] = ++last_node;
}
if(right_node[ind] == -1){
right_node[ind] = ++last_node;
}
if(tl > m){
return get_val(right_node[ind], tl, tr, m+1, r);
}else if(tr <= m){
return get_val(left_node[ind], tl, tr, l, m);
}else{
return get_val(left_node[ind], tl, m, l, m)+get_val(right_node[ind], m+1, tr, m+1, r);
}
}
}
/*
void update(int node, int l, int r) {
push_lazy(node);
if (l == segtree[node].tl && r == segtree[node].tr) {
segtree[node].lazy = 1;
push_lazy(node);
} else {
int mid = (segtree[node].tl + segtree[node].tr) / 2;
if (segtree[node].l == -1) {
segtree[node].l = cnt++;
segtree[segtree[node].l].tl = segtree[node].tl;
segtree[segtree[node].l].tr = mid;
}
if (segtree[node].r == -1) {
segtree[node].r = cnt++;
segtree[segtree[node].r].tl = mid + 1;
segtree[segtree[node].r].tr = segtree[node].tr;
}
if (l > mid) update(segtree[node].r, l, r);
else if (r <= mid) update(segtree[node].l, l, r);
else {
update(segtree[node].l, l, mid);
update(segtree[node].r, mid + 1, r);
}
push_lazy(segtree[node].l);
push_lazy(segtree[node].r);
segtree[node].sum =
segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
}
}
*/
inline void upd(ll ind, ll tl, ll tr, ll l, ll r){
pushdownwards(ind, l, r);
if(tl == l && tr == r){
lazy[ind] = 1;
pushdownwards(ind, l, r);
}else{
ll m = (l+r)/2;
if(left_node[ind] == -1){
left_node[ind] = ++last_node;
}
if(right_node[ind] == -1){
right_node[ind] = ++last_node;
}
if(tl > m){upd(right_node[ind], tl, tr, m+1, r);}
else if(tr <= m){upd(left_node[ind], tl, tr, l, m);}
else{
upd(left_node[ind], tl, m, l, m);
upd(right_node[ind], m+1, tr, m+1, r);
}
pushdownwards(left_node[ind], l, m);
pushdownwards(right_node[ind], m+1, r);
val[ind] = val[left_node[ind]] + val[right_node[ind]];
}
}
void dfs(ll ind, string str){
cout << str << " " << val[ind] << endl;
if(left_node[ind] != -1){
dfs(left_node[ind], str+"L");
}
if(right_node[ind] != -1){
dfs(right_node[ind], str+"R");
}
}
void solve(){
cin >> m;
c = 0;
last_node = 0;
val.assign(MAX_CONST,0);
left_node.assign(MAX_CONST,-1);
right_node.assign(MAX_CONST,-1);
lazy.assign(MAX_CONST, 0);
seg = ++last_node;
for(ll i=0; i<m; i++){
ll opr,l,r;
cin >> opr >> l >> r;
if(opr == 1){
ll res = get_val(1, l+c, r+c, 0, MAX_N);
c = res;
cout << res << "\n";
}else{
upd(1, l+c, r+c, 0, MAX_N);
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
solve();
}
Compilation message
apple.cpp: In function 'void pushdownwards(ll, ll, ll)':
apple.cpp:71:6: warning: unused variable 'm' [-Wunused-variable]
71 | ll m = (l+r)/2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
156756 KB |
Output is correct |
| 2 |
Correct |
56 ms |
157160 KB |
Output is correct |
| 3 |
Correct |
55 ms |
156752 KB |
Output is correct |
| 4 |
Correct |
62 ms |
157016 KB |
Output is correct |
| 5 |
Correct |
64 ms |
157008 KB |
Output is correct |
| 6 |
Correct |
64 ms |
157012 KB |
Output is correct |
| 7 |
Correct |
77 ms |
157012 KB |
Output is correct |
| 8 |
Correct |
142 ms |
157832 KB |
Output is correct |
| 9 |
Correct |
249 ms |
159056 KB |
Output is correct |
| 10 |
Correct |
234 ms |
159088 KB |
Output is correct |
| 11 |
Correct |
232 ms |
159060 KB |
Output is correct |
| 12 |
Correct |
235 ms |
159060 KB |
Output is correct |
| 13 |
Correct |
189 ms |
159572 KB |
Output is correct |
| 14 |
Correct |
196 ms |
159568 KB |
Output is correct |
| 15 |
Execution timed out |
2483 ms |
262144 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
