#include <bits/stdc++.h>
using namespace std;
inline void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
class SEGMENT_TREE
{
private:
int tree_size;
vector<int> tree_min, tree_max;
inline void Update(int ind, int l, int r, int x, int v)
{
if (r < x || x < l)
{
return;
}
if (l == r)
{
tree_min[ind] = min(tree_min[ind], v);
tree_max[ind] = max(tree_max[ind], v);
return;
}
int m = (l + r) >> 1;
Update(ind << 1, l, m, x, v);
Update(ind << 1 | 1, m + 1, r, x, v);
tree_min[ind] = min(tree_min[ind << 1], tree_min[ind << 1 | 1]);
tree_max[ind] = max(tree_max[ind << 1], tree_max[ind << 1 | 1]);
}
inline int Get(int ind, int l, int r, int x, int y, bool mode)
{
if (r < x || y < l)
{
return (mode ? 1e9 : -1e9);
}
if (x <= l && r <= y)
{
return (mode ? tree_min[ind] : tree_max[ind]);
}
int m = (l + r) >> 1;
if (mode)
{
return min(Get(ind << 1, l, m, x, y, mode), Get(ind << 1 | 1, m + 1, r, x, y, mode));
}
return max(Get(ind << 1, l, m, x, y, mode), Get(ind << 1 | 1, m + 1, r, x, y, mode));
}
public:
inline SEGMENT_TREE(int new_size)
{
tree_size = new_size;
tree_min.resize(tree_size << 2, 1e9);
tree_max.resize(tree_size << 2, -1e9);
}
inline void Update(int x, int v)
{
Update(1, 1, tree_size, x, v);
}
inline int GetMin(int x, int y)
{
return Get(1, 1, tree_size, x, y, 1);
}
inline int GetMax(int x, int y)
{
return Get(1, 1, tree_size, x, y, 0);
}
} st1(450000), st2(450000);
struct BEAVER
{
int X, Y, Z;
};
int n, m, b[450000], l, r, mid, x, res = -1, c, d, e;
BEAVER a[150000];
inline bool comp(const BEAVER & ina, const BEAVER & inb)
{
return ina.X < inb.X;
}
int main()
{
setup();
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i].X >> a[i].Y >> a[i].Z;
b[i * 3] = a[i].X;
b[i * 3 + 1] = a[i].Y;
b[i * 3 + 2] = a[i].Z;
}
sort(a, a + n, comp);
sort(b, b + 3 * n);
m = unique(b, b + 3 * n) - b;
for (int i = 0, j = 0; i < n; ++i)
{
a[i].X = lower_bound(b, b + m, a[i].X) - b + 1;
a[i].Y = lower_bound(b, b + m, a[i].Y) - b + 1;
a[i].Z = lower_bound(b, b + m, a[i].Z) - b + 1;
while (a[i].X != a[j].X)
{
st1.Update(a[j].Y, a[j].Z);
c = st1.GetMax(1, a[j].Y - 1);
if (c > a[j].Z)
{
st2.Update(a[j].Y, c);
}
l = a[j].Y + 1;
r = 450000;
x = -1;
while (l <= r)
{
e = (l + r) >> 1;
if (st1.GetMin(e, 450000) < a[j].Z)
{
x = e;
l = e + 1;
}
else
{
r = e - 1;
}
}
if (x != -1)
{
st2.Update(x, a[j].Z);
}
j++;
}
l = a[i].Y + 1;
r = 450000;
x = -1;
while (l <= r)
{
e = (l + r) >> 1;
if (st2.GetMax(e, 450000) > a[i].Z)
{
x = e;
l = e + 1;
}
else
{
r = e - 1;
}
}
if (x != -1)
{
res = max(res, b[a[i].X - 1] + b[x - 1] + b[st2.GetMax(x, 450000) - 1]);
}
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |