// Be name khoda //
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn5 = 2e5 + 10;
const int maxnt = 8e5 + 10;
const ll inf = 1e18;
int n;
struct segment_tree_bs{
ll mx[maxnt];
int get_first(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq || mx[v] <= val)
return n;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
int ans = get_first(l, mid, lq, rq, val, v * 2);
if(ans != n)
return ans;
return get_first(mid, r, lq, rq, val, v * 2 + 1);
}
ll get_max(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return -inf;
if(lq <= l && r <= rq)
return mx[v];
int mid = (l + r) >> 1;
return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
}
void update(int l, int r, int id, ll val, int v){
if(r - l == 1){
mx[v] = val;
return;
}
int mid = (l + r) >> 1;
if(id < mid)
update(l, mid, id, val, v * 2);
else
update(mid, r, id, val, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
return;
}
} val3_stored;
struct segment_tree_val2_plus_mx_val3{
ll mxval2[maxnt], mxval3[maxnt], mx[maxnt];
bool newval[maxnt];
void build(){
fill(mxval2, mxval2 + maxnt, -inf);
fill(mxval3, mxval3 + maxnt, -inf);
fill(mx, mx + maxnt, -inf);
memset(newval, false, sizeof newval);
return;
}
void shift(int v){
if(!newval[v])
return;
newval[v] = false;
mxval3[v * 2] = mxval3[v * 2 + 1] = mxval3[v];
newval[v * 2] = newval[v * 2 + 1] = true;
mx[v * 2] = mxval2[v * 2] + mxval3[v];
mx[v * 2 + 1] = mxval2[v * 2 + 1] + mxval3[v];
return;
}
void update_doone(int l, int r, int id, ll val, int v){
if(r - l == 1){
mxval2[v] = val;
mx[v] = val + mxval3[v];
return;
}
int mid = (l + r) >> 1; shift(v);
if(id < mid)
update_doone(l, mid, id, val, v * 2);
else
update_doone(mid, r, id, val, v * 2 + 1);
mxval2[v] = max(mxval2[v * 2], mxval2[v * 2 + 1]);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
void sset(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
newval[v] = true;
mxval3[v] = val;
mx[v] = val + mxval2[v];
return;
}
int mid = (l + r) >> 1; shift(v);
sset(l, mid, lq, rq, val, v * 2);
sset(mid, r, lq, rq, val, v * 2 + 1);
mx[v] = mx[v * 2] + mx[v * 2 + 1];
return;
}
ll get_max(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return -inf;
if(lq <= l && r <= rq)
return mx[v];
int mid = (l + r) >> 1; shift(v);
return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
}
} main_seg;
int pos2[maxn5], per1[maxn5], per2[maxn5];
ll bsval2[maxn5], val1[maxn5], val2[maxn5], val3[maxn5];
vector <int> toadd;
bool cmp1(int i, int j){return val1[i] < val1[j];}
bool cmp2(int i, int j){return val2[i] < val2[j];}
inline void add(int v){
main_seg.update_doone(0, n, pos2[v], val2[v], 1);
if(val3_stored.get_max(0, n, 0, pos2[v], 1) <= val3[v]){
int last = val3_stored.get_first(0, n, pos2[v], n, val3[v] - 1, 1);
main_seg.sset(0, n, pos2[v] + 1, last, val3[v], 1);
main_seg.sset(0, n, pos2[v], pos2[v] + 1, -inf, 1);
}
val3_stored.update(0, n, pos2[v], val3[v], 1);
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> val1[i] >> val2[i] >> val3[i];
per1[i] = per2[i] = i;
}
sort(per1, per1 + n, cmp1); // bar hasbe val1
sort(per2, per2 + n, cmp2); // bar hasbe val2
for(int i = 0; i < n; i++){
pos2[per2[i]] = i;
bsval2[i] = val2[per2[i]];
}
main_seg.build(); // hame ro bezar -inf
// val3_stored.build(0, n, 1); // hame ro bezar 0
ll ans = -1;
for(int i = 0; i < n; i++){
int v = per1[i];
while(toadd.size() && val1[toadd.back()] < val1[v]){
add(toadd.back());
toadd.pop_back();
}
int pt1 = upper_bound(bsval2, bsval2 + n, val2[v]) - bsval2;
int pt2 = val3_stored.get_first(0, n, 0, n, val3[v], 1); // avalin kasi ke az akidan val3 bishtar darad, agar nabood n midahad
int pt = max(pt1, pt2);
ans = max(ans, main_seg.get_max(0, n, pt, n, 1) + val1[v]);
toadd.pb(v);
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
19820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
19820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
19924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
19924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
19924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
19924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
19820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
