#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;
bool 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 ;
}
add(node);
push(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 (node->ptrL == NULL ? 0 : query(node->ptrL, a, b)) + (node->ptrR == NULL ? 0 : query(node->ptrR, a, b));
}
Node *root = new Node(1, 1e9);
int M, D, X, Y, C = 0;
int main() {
fast
cin >> M;
while (M--) {
cin >> D >> X >> Y;
if (D == 1) {
C = query(root, X + C, Y + C);
cout << C << "\n";
} else
update(root, X + C, Y + C);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
