#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
const ll INF = 1e12;
const ll N =(1e7+5); // TODO : change value as per problem
const ll MOD = 1e9+7;
ll lazy[4*N];
ll tree[4*N];
void updateRange(int node, int start, int end, int l, int r, int val)
{
if(lazy[node] != 0)
{
tree[node] = (end - start + 1) * lazy[node];
if(start != end)
{
if(!lazy[node*2]) lazy[node*2] = 1;
if(!lazy[node*2+1]) lazy[node*2+1] = 1;
}
lazy[node] = 0; // Reset it
}
if(start > end or start > r or end < l) // Current segment is not within range [l, r]
return;
if(start >= l and end <= r)
{
// Segment is fully within range
lazy[node] =val;
tree[node] = (end - start + 1) * lazy[node];
if(start != end)
{
// Not leaf node
if(!lazy[node*2]) lazy[node*2] = 1;
if(!lazy[node*2+1]) lazy[node*2+1] = 1;
}
lazy[node] = 0;
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val); // Updating left child
updateRange(node*2 + 1, mid + 1, end, l, r, val); // Updating right child
tree[node] = tree[node*2] + tree[node*2+1]; // Updating root with max value
}
int queryRange(int node, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return 0; // Out of range
if(lazy[node] != 0)
{
// This node needs to be updated
tree[node] = (end - start + 1) * lazy[node];//pdate it
if(start != end)
{
if(!lazy[node*2]) lazy[node*2] = 1;
if(!lazy[node*2+1]) lazy[node*2+1] = 1;
}
lazy[node] = 0; // Reset it
}
if(start >= l and end <= r) // Current segment is totally within range [l, r]
return tree[node];
int mid = (start + end) / 2;
int p1 = queryRange(node*2, start, mid, l, r); // Query left child
int p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
return (p1 + p2);
}
void solve(){
ll q;
cin >> q;
ll c = 0;
while(q--){
ll t;
cin >> t;
if(t == 1){
ll l,r;
cin >> l >> r;
l+=c;
r += c;
ll x = queryRange(1,1,1e7,l,r);
cout << x << endl;
c = x;
}
else{
ll l,r;
cin >> l >> r;
l += c;
r += c;
updateRange(1,1,1e7,l,r,1);
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
ll tt=1;
// cin >> tt;
while(tt--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
35 ms |
34296 KB |
Output is correct |
| 5 |
Correct |
42 ms |
39416 KB |
Output is correct |
| 6 |
Correct |
39 ms |
36224 KB |
Output is correct |
| 7 |
Correct |
43 ms |
39672 KB |
Output is correct |
| 8 |
Correct |
244 ms |
189692 KB |
Output is correct |
| 9 |
Correct |
391 ms |
253560 KB |
Output is correct |
| 10 |
Runtime error |
262 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Halted |
0 ms |
0 KB |
- |
