#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <array>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <memory>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#ifdef DBG
#define dbg 1
#define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define dbg 0
#define dpf(...) 42
#endif
#define SIZE(c) int((c).size())
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;
template <typename T> inline void UpdateMax(T& x, T v) { x = max(x, v); }
template <typename T> inline void UpdateMin(T& x, T v) { x = min(x, v); }
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
// Dynamic Segment Tree base class.
class SegTree {
public:
struct Node {
int l = -1, r = -1;
int sum = 0;
char set = 0;
};
vector<Node> a;
int max_idx;
using T = Node;
SegTree() {}
inline virtual void CombineNode(const T& lv, const T& rv, T& v) {
v.sum = lv.sum + rv.sum;
}
void Init(int max_idx, int init_max_update = 0) {
assert(max_idx >= -1);
this->max_idx = max_idx;
int m = max_idx + 1;
int c = 1;
while (m) {
++c;
m >>= 1;
}
a.resize(1);
a[0] = Node();
a.reserve(1 + c * init_max_update);
}
void RangeSet(int l, int r) { RangeSet(l, r, 0, max_idx, 0); }
int QuerySum(int l, int r) { return QuerySum(l, r, 0, max_idx, 0); }
void Debug() {
if (!dbg) return;
for(int i=0;i<SIZE(a);++i) {
dpf("%d: %d %d, %d %d\n", i, a[i].sum, a[i].set, a[i].l, a[i].r);
}
}
protected:
inline void ApplySet(int l,int r,int p) {
a[p].sum = r - l + 1;
a[p].set = 1;
}
// Update p's children's lazy tags.
virtual void PushDown(int l, int r, int p) {
if (a[p].l < 0) {
a[p].l = SIZE(a);
a.emplace_back();
}
if (a[p].r < 0) {
a[p].r = SIZE(a);
a.emplace_back();
}
int m = (l + r) >> 1;
if (a[p].set) {
ApplySet(l, m, a[p].l);
ApplySet(m + 1, r, a[p].r);
a[p].set = 0;
}
}
// Combines left and right children to current node.
inline void PushUp(int p) { CombineNode(a[a[p].l], a[a[p].r], a[p]); }
private:
void RangeSet(int ql, int qr, int l, int r, int p) {
dpf("RangeSet: %d %d, %d %d %d\n",ql,qr,l,r,p);
if (ql > r || qr < l) return;
if (ql <= l && qr >= r) {
ApplySet(l, r, p);
return;
}
PushDown(l, r, p);
int m = (l + r) >> 1;
RangeSet(ql, qr, l, m, a[p].l);
RangeSet(ql, qr, m + 1, r, a[p].r);
PushUp(p);
}
int QuerySum(int ql, int qr, int l, int r, int p) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return a[p].sum;
PushDown(l, r, p);
int m = (l + r) >> 1;
int res =
QuerySum(ql, qr, l, m, a[p].l) + QuerySum(ql, qr, m + 1, r, a[p].r);
PushUp(p);
return res;
}
};
SegTree st;
int Query(int l, int r) { return st.QuerySum(l, r); }
void Update(int l, int r) { st.RangeSet(l, r); }
void Solve() {
int nq;
scanf("%d",&nq);
st.Init(1000000000, nq);
int C = 0;
while(nq--) {
int t,l,r;
scanf("%d%d%d",&t,&l,&r);
dpf("Query %d %d %d\n", t, l, r);
l += C, r += C;
if(t==1) {
C = Query(l, r);
printf("%d\n", C);
} else {
Update(l, r);
}
st.Debug();
}
}
int main() {
int t = 1;
// scanf("%d", &t);
for (int i = 1; i <= t; ++i) {
Solve();
}
return 0;
}
Compilation message
apple.cpp: In member function 'void SegTree::Debug()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:95:7: note: in expansion of macro 'dpf'
95 | dpf("%d: %d %d, %d %d\n", i, a[i].sum, a[i].set, a[i].l, a[i].r);
| ^~~
apple.cpp: In member function 'void SegTree::RangeSet(int, int, int, int, int)':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:128:5: note: in expansion of macro 'dpf'
128 | dpf("RangeSet: %d %d, %d %d %d\n",ql,qr,l,r,p);
| ^~~
apple.cpp: In function 'void Solve()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:168:5: note: in expansion of macro 'dpf'
168 | dpf("Query %d %d %d\n", t, l, r);
| ^~~
apple.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d",&nq);
| ~~~~~^~~~~~~~~~
apple.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d%d%d",&t,&l,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1860 KB |
Output is correct |
| 5 |
Correct |
14 ms |
2344 KB |
Output is correct |
| 6 |
Correct |
15 ms |
2252 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2300 KB |
Output is correct |
| 8 |
Correct |
102 ms |
15560 KB |
Output is correct |
| 9 |
Correct |
217 ms |
26364 KB |
Output is correct |
| 10 |
Correct |
220 ms |
29132 KB |
Output is correct |
| 11 |
Correct |
217 ms |
31116 KB |
Output is correct |
| 12 |
Correct |
204 ms |
32116 KB |
Output is correct |
| 13 |
Correct |
206 ms |
37312 KB |
Output is correct |
| 14 |
Correct |
245 ms |
37560 KB |
Output is correct |
| 15 |
Correct |
292 ms |
98380 KB |
Output is correct |
| 16 |
Correct |
316 ms |
98452 KB |
Output is correct |
| 17 |
Correct |
193 ms |
38844 KB |
Output is correct |
| 18 |
Correct |
204 ms |
38792 KB |
Output is correct |
| 19 |
Correct |
313 ms |
98256 KB |
Output is correct |
| 20 |
Correct |
306 ms |
98328 KB |
Output is correct |
