#include <bits/stdc++.h> // QioCas
#ifdef LOCAL
#include </home/cas/Cp/Lib/debug.h>
#else
#define console(...) void(202421)
#endif
using namespace std;
using ll = long long;
int Q;
struct node_t {
int sum = 0, maxL = 0, maxR = 0, ans = 0, sz = 0, lz = 0;
node_t *l = nullptr, *r = nullptr;
void update(node_t* u, node_t* v) {
sum = u->sum + v->sum;
maxL = max(u->maxL, (u->sum == u->sz ? u->sum + v->maxL : 0));
maxR = max(v->maxR, (v->sum == v->sz ? v->sum + u->maxR : 0));
ans = max({u->ans, v->ans, u->maxR + v->maxL});
}
node_t() = default;
node_t(int sz): sz(sz) {}
};
using pnode = node_t*;
void update_node(pnode& IT, int l, int r) {
if(!IT) IT = new node_t(r - l + 1);
IT->sum = IT->maxL = IT->maxR = IT->ans = r - l + 1;
IT->lz = 1;
}
void push_down(pnode& IT, int l, int r) {
if(IT->lz == 0) return;
if(IT->lz == 1) {
int mid = (l + r) / 2;
update_node(IT->l, l, mid);
update_node(IT->r, mid + 1, r);
}
IT->lz = 2;
}
void update(pnode& IT, int l, int r, int s, int t) {
if(!IT) IT = new node_t(r - l + 1);
if(l > t || r < s) return;
if(s <= l && r <= t) {
update_node(IT, l, r);
return;
} push_down(IT, l, r);
int mid = (l + r) / 2;
update(IT->l, l, mid, s, t);
update(IT->r, mid + 1, r, s, t);
IT->update(IT->l, IT->r);
}
pnode prod(pnode& IT, int l, int r, int s, int t) {
if(!IT || l > t || r < s) return new node_t();
if(s <= l && r <= t) return IT;
push_down(IT, l, r);
int mid = (l + r) / 2;
pnode ret = new node_t();
ret->update(prod(IT->l, l, mid, s, t), prod(IT->r, mid + 1, r, s, t));
return ret;
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> Q;
ll c = 0;
pnode root = new node_t();
int L = 1, R = 1e9;
while(Q--) {
int op; ll l, r;
cin >> op >> l >> r;
l += c; r += c;
if(op == 2) {
update(root, L, R, l, r);
} else {
int x = prod(root, L, R, l, r)->ans;
cout << x << "\n";
c += x;
}
}
return 0;
}
////////////////////////////////////////////////////////////////////////////
// Nhân quả không nợ chúng ta thức gì, cho nên xin đừng oán giận ////////
// _
// _oo0oo_
// o8888888o
// 88” . “88
// (| -_- |)
// O\ = /O
// ____/'---'\____
// .' \\| |// '.
// / \\||| : |||// \
// / _||||| -:- |||||_ \
// | | \\\ - /'| | |
// | \_| `\`---'// |_/ |
// \ .-\__ `-. -'__/-. /
// ___`. .' /--.--\ `. . '___
// ."" '< `.___\_<|>_/___.' _> \"".
// | | : `- \`. ;`. _/; .'/ / .' ; |
// \ \ `-. \_\_`. _.' _/_/ -' _.' /
//===================`-.`___`-.__\ \___ /__.-'_.'_.-'===================//
// `=--=-'
// Đức Phật nơi đây phù hộ code con chạy không Bugs. Nam mô a di đà Phật.
//
// _.-/`)
// // / / )
// .=// / / / )
// //`/ / / / /
// // / ` /
// || /
// || /
// \\ /
// )) .'
// // /
//
Compilation message
apple.cpp:103:1: warning: multi-line comment [-Wcomment]
103 | // / \\||| : |||// \
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
