#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
/*
struct Node
{
int node, len;
Node() {node = len = 0;}
Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/
#define MOD 1000000007
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)
#define testBit(n, bit) ((n >> bit) & 1)
#define flipBit(n, bit) (n ^ (1ll << bit))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
const ll MAX = 1e18;
class Node{
private:
ll lo, hi, cnt;
bool stop;
Node *left, *right;
public:
Node(ll lo, ll hi): lo(lo), hi(hi){
cnt = 0; stop = true;
left = nullptr, right = nullptr;
}
Node(): Node(1, MAX){}
void update(ll posL, ll posR){
if (posR < lo || hi < posL) return;
if (posL <= lo && hi <= posR){
cnt = hi - lo + 1;
stop = true;
delete left; left = nullptr;
delete right; right = nullptr;
return;
}
if (stop){
if (cnt) return;
stop = false;
ll mid = (lo + hi) >> 1;
left = new Node(lo, mid);
right = new Node(mid + 1, hi);
}
left -> update(posL, posR);
right -> update(posL, posR);
cnt = left -> cnt + right -> cnt;
}
ll get(ll posL, ll posR){
if (posR < lo || hi < posL) return 0;
if (posL <= lo && hi <= posR) return cnt;
if (stop){
if (!cnt) return 0;
if (posR <= hi)
return posR - lo + 1;
else
return hi - posL + 1;
}
return left -> get(posL, posR) + right -> get(posL, posR);
}
};
Node *root = new Node();
ll m, c;
main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> m; c = 0;
FOR(ll, _, 1, m){
ll d, x, y; cin >> d >> x >> y;
if (d == 1){
c = root -> get(x + c, y + c);
cout << c << '\n';
} else
root -> update(x + c, y + c);
}
}
Compilation message
apple.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
103 | main()
| ^~~~
# |
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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |