#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<int, 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 int MAX = 1000000000;
class Node{
private:
Node *left, *right;
bool stop;
int lo, hi, cnt;
public:
Node(int lo, int hi, bool all = false): lo(lo), hi(hi){
left = nullptr, right = nullptr;
stop = true;
cnt = all ? (hi - lo + 1) : 0;
}
Node(): Node(1, MAX){}
void ripen(int posL, int posR){
if (hi < posL || posR < lo) return;
if (posL <= lo && hi <= posR){
stop = true;
cnt = hi - lo + 1;
if (left != nullptr){
delete left;
left = nullptr;
}
if (right != nullptr){
delete right;
right = nullptr;
}
return;
}
if (stop){
if (cnt) return;
int mid = (lo + hi) >> 1;
stop = false;
left = new Node(lo, mid);
right = new Node(mid + 1, hi);
}
left -> ripen(posL, posR);
right -> ripen(posL, posR);
cnt = left -> cnt + right -> cnt;
}
int get(int posL, int posR){
if (hi < posL || posR < lo) return 0;
// cerr << lo << '/' << hi << ' ' << stop << '.' << cnt << '\n';
if (posL <= lo && hi <= posR) return cnt;
// cerr << "someOut\n";
if (this -> stop){
if (cnt == 0) return 0;
if (posR <= hi)
return posR - lo + 1;
else
return hi - posL + 1;
}
// cerr << "nonstop\n";
return left -> get(posL, posR) + right -> get(posL, posR);
}
};
Node *root = new Node();
int m, c;
main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> m; c = 0;
FOR(int, _, 1, m){
int d, x, y; cin >> d >> x >> y;
if (d == 1){
int ans = root -> get(x + c, y + c);
cout << ans << '\n';
c = ans;
} else
root -> ripen(x + c, y + c);
}
}
Compilation message
apple.cpp:113:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
113 | 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 |
- |
