#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;
struct Node {
int l, r, sum, lazy;
Node *ptrL, *ptrR;
Node(int a, int b) : l(a), r(b), sum(0), lazy(0), ptrL(NULL), ptrR(NULL) { };
};
void add(Node *node) {
if (node->ptrL == NULL && node->l != node->r) {
int mid = (node->l + node->r) / 2;
node->ptrL = new Node(node->l, mid);
node->ptrR = new Node(mid+1, node->r);
}
}
void push(Node *node) {
if (node->lazy) {
node->sum = node->r - node->l + 1;
if (node->l != node->r) {
add(node);
node->ptrL->lazy = 1;
node->ptrR->lazy = 1;
}
node->lazy = 0;
}
}
void update(Node *node, int a, int b) {
if (node->l > b || a > node->r)
return ;
if (a <= node->l && node->r <= b) {
node->lazy = 1;
push(node);
return ;
}
push(node);
add(node);
update(node->ptrL, a, b);
update(node->ptrR, a, b);
node->sum = node->ptrL->sum + node->ptrR->sum;
}
int query(Node *node, int a, int b) {
push(node);
if (node->l > b || a > node->r)
return 0;
if (a <= node->l && node->r <= b)
return node->sum;
add(node);
return query(node->ptrL, a, b) + query(node->ptrR, a, b);
}
int main() {
fast
int M, D, X, Y;
cin >> M;
Node *root = new Node(1, 1e9);
int C = 0;
while (M--) {
cin >> D >> X >> Y;
X += C, Y += C;
if (D == 1) {
C = query(root, X, Y);
cout << C << "\n";
} else
update(root, X, Y);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
