//{{{
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}
// clang-format off
constexpr int NODES = 1.5e7;
// 1.5e7 * 4int ~ 256MB, 6e5 op in 1s
#define lson(x) (node[x].lc)
#define rson(x) (node[x].rc)
struct Node {
int lc, rc;
int mset, sum;
} node[NODES];
struct segtree{ // TODO pay special attention to MEM LIMIT!!
static const int NO_OP = INT_MAX - 1;
int _n, cnt;
segtree(int n) : _n(n), cnt(0) { new_node(1, n + 1); };
inline int new_node(int lx, int rx) {
++cnt;
node[cnt].sum = 0;
node[cnt].mset = NO_OP;
return cnt;
}
inline void pushup(int x) { // 1
node[x].sum = node[lson(x)].sum + node[rson(x)].sum;
}
inline void push(int x, int lx, int rx, int mid) {
if (!node[x].lc) node[x].lc = new_node(lx, mid), node[x].rc = new_node(mid, rx);
int& mset = node[x].mset;
if (mset != NO_OP) {
node[lson(x)].sum = (mid - lx) * mset;
node[lson(x)].mset = mset;
node[rson(x)].sum = (rx - mid) * mset;
node[rson(x)].mset = mset;
mset = NO_OP;
}
}
void set(int x, int lx, int rx, int l, int r, int v) {
if (r <= lx || rx <= l) return;
if (l <= lx && rx <= r) {
node[x].mset = v;
node[x].sum = (rx - lx) * v;
return;
}
int mid = lx + (rx - lx) / 2;
push(x, lx, rx, mid);
if(l < mid) set(lson(x), lx, mid, l, r, v);
if(r > mid) set(rson(x), mid, rx, l, r, v);
pushup(x);
}
int query(int x, int lx, int rx, int l, int r) {
if (r <= lx || rx <= l) return 0;
if (l <= lx && rx <= r) return node[x].sum;
int mid = lx + (rx - lx) / 2;
push(x, lx, rx, mid);
int vl = 0, vr = 0;
if(l < mid) vl = query(lson(x), lx, mid, l, r);
if(r > mid) vr = query(rson(x), mid, rx, l, r);
return vl + vr; // 3
}
};
// clang-format on
int readint() // for integer
{
char c;
while (c = getchar(), '-' != c && !isdigit(c))
if (c == EOF) return EOF;
int f = 1;
if ('-' == c) f = -1, c = getchar();
int x = c - '0';
while (isdigit(c = getchar())) x = x * 10 + c - '0';
return x * f;
}
void write(int a) // NOTICE a >= 0
{
if (a > 9) write(a / 10);
putchar(a % 10 + '0');
}
int m;
int op, x, y;
int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
while (~scanf("%d", &m))
{
int n = 1000000000;
segtree tree(n);
int c = 0;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &op, &x, &y);
if (op == 2)
{
y++;
tree.set(1, 1, n + 1, x + c, y + c, 1);
}
else
{
y++;
int ans = tree.query(1, 1, n + 1, x + c, y + c);
printf("%d\n", ans);
c = ans;
}
}
}
return 0;
}
Compilation message
apple.cpp: In function 'int main()':
apple.cpp:134:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
134 | scanf("%d%d%d", &op, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
10 ms |
2028 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2412 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2284 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
88 ms |
15852 KB |
Output is correct |
| 9 |
Correct |
189 ms |
27372 KB |
Output is correct |
| 10 |
Correct |
190 ms |
30060 KB |
Output is correct |
| 11 |
Correct |
199 ms |
32512 KB |
Output is correct |
| 12 |
Correct |
200 ms |
33260 KB |
Output is correct |
| 13 |
Correct |
177 ms |
38636 KB |
Output is correct |
| 14 |
Correct |
177 ms |
39020 KB |
Output is correct |
| 15 |
Correct |
253 ms |
69356 KB |
Output is correct |
| 16 |
Correct |
256 ms |
69856 KB |
Output is correct |
| 17 |
Correct |
181 ms |
40172 KB |
Output is correct |
| 18 |
Correct |
184 ms |
40232 KB |
Output is correct |
| 19 |
Correct |
263 ms |
71276 KB |
Output is correct |
| 20 |
Correct |
259 ms |
71276 KB |
Output is correct |
