#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
return t.size();
}
template<typename T, size_t N>
int SIZE(T (&t)[N]){
return N;
}
string to_string(char t){
return "'" + string({t}) + "'";
}
string to_string(bool t){
return t ? "true" : "false";
}
string to_string(const string &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += t[i];
}
return '"' + ret + '"';
}
string to_string(const char* t){
string ret(t);
return to_string(ret);
}
template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
ret += t[i] + '0';
}
return to_string(ret);
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);
template<typename T, typename S>
string to_string(const pair<T, S> &t){
return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
string ret = "[";
x1 = min(x1, SIZE(t));
auto e = begin(t);
advance(e,x1);
for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += to_string(*e, C...) + (i != _i ? ", " : "");
e = next(e);
}
return ret + "]";
}
template<int Index, typename... Ts>
struct print_tuple{
string operator() (const tuple<Ts...>& t) {
string ret = print_tuple<Index - 1, Ts...>{}(t);
ret += (Index ? ", " : "");
return ret + to_string(get<Index>(t));
}
};
template<typename... Ts>
struct print_tuple<0, Ts...> {
string operator() (const tuple<Ts...>& t) {
return to_string(get<0>(t));
}
};
template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
const auto Size = tuple_size<tuple<Ts...>>::value;
return print_tuple<Size - 1, Ts...>{}(t);
}
void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
cout << to_string(H) << " | ";
dbgr(T...);
}
void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
cout << H << " ";
dbgs(T...);
}
/*
formatted functions:
*/
/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)
/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
/*
000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
DO IT NOW!!!
*/
using u128=__uint128_t;
using i128=__int128;
const int mod=1000000007;
const int N=100005;
const int LOG=30;
const int MX=N*LOG*2;
const int inf=1e9;
const double eps=1e-11;
string s;
int n, m, k, qq;
struct Node {
int l, r, cnt, lptr, rptr;
bool lazy;
Node() {
l=0, r=0, cnt=0, lptr=-1, rptr=-1, lazy=false;
};
Node(int x, int y) {
l=x, r=y, cnt=0, lptr=-1, rptr=-1, lazy=false;
};
};
Node t[MX];
int cur=1;
void propogate(int v) {
int mid=(t[v].l+t[v].r)/2;
if (t[v].lptr==-1) {
t[v].lptr=cur++;
t[t[v].lptr]=Node(t[v].l, mid);
}
if (t[v].rptr==-1) {
t[v].rptr=cur++;
t[t[v].rptr]=Node(mid+1, t[v].r);
}
if (t[v].lazy) {
t[t[v].lptr].lazy=t[t[v].rptr].lazy=true;
t[t[v].lptr].cnt=t[t[v].lptr].r-t[t[v].lptr].l+1;
t[t[v].rptr].cnt=t[t[v].rptr].r-t[t[v].rptr].l+1;
}
}
void update(int ql, int qr, int v=0) {
if (ql>t[v].r || qr<t[v].l) return;
if (ql<=t[v].l && qr>=t[v].r) {
t[v].cnt=t[v].r-t[v].l+1, t[v].lazy=true;
return;
}
propogate(v);
int mid=(t[v].l+t[v].r)/2;
update(ql, qr, t[v].lptr);
update(ql, qr, t[v].rptr);
t[v].cnt=t[t[v].lptr].cnt+t[t[v].rptr].cnt;
}
int query(int ql, int qr, int v=0) {
if (ql>t[v].r || qr<t[v].l) return 0;
if (ql<=t[v].l && qr>=t[v].r) {
return t[v].cnt;
}
propogate(v);
int mid=(t[v].l+t[v].r)/2;
return query(ql, qr, t[v].lptr)+query(ql, qr, t[v].rptr);
}
void solve() {
cin>>n;
int C=0;
t[0].l=0, t[0].r=(1<<LOG)-1;
for (int i=0; i<n; i++) {
int d, x, y;
cin>>d>>x>>y;
if (d==1) {
C=query(x+C, y+C);
cout<<C<<"\n";
}
else {
update(x+C, y+C);
}
}
/*
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
*/
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Compilation message
apple.cpp: In function 'void update(int, int, int)':
apple.cpp:222:6: warning: unused variable 'mid' [-Wunused-variable]
222 | int mid=(t[v].l+t[v].r)/2;
| ^~~
apple.cpp: In function 'int query(int, int, int)':
apple.cpp:235:6: warning: unused variable 'mid' [-Wunused-variable]
235 | int mid=(t[v].l+t[v].r)/2;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
141132 KB |
Output is correct |
| 2 |
Correct |
64 ms |
141164 KB |
Output is correct |
| 3 |
Correct |
62 ms |
141132 KB |
Output is correct |
| 4 |
Correct |
74 ms |
141192 KB |
Output is correct |
| 5 |
Correct |
81 ms |
141204 KB |
Output is correct |
| 6 |
Correct |
75 ms |
141152 KB |
Output is correct |
| 7 |
Correct |
71 ms |
141176 KB |
Output is correct |
| 8 |
Correct |
133 ms |
141316 KB |
Output is correct |
| 9 |
Correct |
218 ms |
141568 KB |
Output is correct |
| 10 |
Correct |
231 ms |
141600 KB |
Output is correct |
| 11 |
Correct |
233 ms |
141480 KB |
Output is correct |
| 12 |
Correct |
241 ms |
141552 KB |
Output is correct |
| 13 |
Correct |
210 ms |
141604 KB |
Output is correct |
| 14 |
Correct |
213 ms |
141664 KB |
Output is correct |
| 15 |
Correct |
267 ms |
141980 KB |
Output is correct |
| 16 |
Correct |
265 ms |
143820 KB |
Output is correct |
| 17 |
Correct |
214 ms |
143784 KB |
Output is correct |
| 18 |
Correct |
231 ms |
143780 KB |
Output is correct |
| 19 |
Correct |
265 ms |
143860 KB |
Output is correct |
| 20 |
Correct |
273 ms |
143824 KB |
Output is correct |
