#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
int n;
struct aint {
int sum, lazy;
aint *st, *dr;
aint() {
st = dr = NULL;
lazy = -1;
sum = 0;
}
}*root;
void push (aint* node, int st, int dr) {
if (node->lazy == -1)
return;
node->sum = (dr - st + 1) * node->lazy;
if (st != dr) {
if (node->st != NULL)
node->st->lazy = node->lazy;
if (node->dr != NULL)
node->dr->lazy = node->lazy;
}
node->lazy = -1;
}
void update (aint* root, int st, int dr, int a, int b) {
if (root->st == NULL) root->st = new aint;
if (root->dr == NULL) root->dr = new aint;
push(root, st, dr);
if (st > dr || b < st || a > dr)
return;
if (a <= st && dr <= b) {
root->sum = dr - st + 1;
if (st != dr) {
root->st->lazy = 1;
root->dr->lazy = 1;
}
return;
}
int mij = (st + dr) / 2;
update(root->st, st, mij, a, b);
update(root->dr, mij + 1, dr, a, b);
root->sum = root->st->sum + root->dr->sum;
}
int query (aint* root, int st, int dr, int a, int b) {
if (root == NULL)
return 0;
push(root, st, dr);
if (st > dr || b < st || a > dr)
return 0;
if (a <= st && dr <= b)
return root->sum;
int mij = (st + dr) / 2;
return (query(root->st, st, mij, a, b) + query(root->dr, mij + 1, dr, a, b));
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
root = new aint;
int c = 0;
for (int i = 1; i <= n; i++) {
int d, x, y;
cin >>d >> x >> y;
x += c; y += c;
if (d == 1) {
c = query(root, 1, INF, x, y);
cout << c << "\n";
}
else {
update(root, 1, INF, x, y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
