#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1<<18; // tem q ser pot de 2 pra seg
struct Pt {
int x, y, z;
bool operator<(const Pt& o) { return z < o.z; }
} pt[maxn];
struct SegmentTree {
int mx[maxn<<1], mn[maxn<<1];
SegmentTree() { for(int i = 0; i < (maxn<<1); i++) mx[i] = -0x3f3f3f3f, mn[i] = 0x3f3f3f3f; }
void upd(int x, int v) {
// printf("upd %d %d\n", x, v);
x += maxn;
for(mx[x] = max(mx[x], v), mn[x] = min(mn[x], v); x > 1; x >>= 1)
mx[x>>1] = max(mx[x], mx[x^1]), mn[x>>1] = min(mn[x], mn[x^1]);
}
int query(int l, int r) {
// maximum in this segment
// printf("query %d %d == ", l, r);
r++;
int ans = -0x3f3f3f3f;
for(l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
if(l&1) ans = max(ans, mx[l++]);
if(r&1) ans = max(ans, mx[--r]);
}
// printf("%d\n", ans);
return ans;
}
int find(int v) {
int x = 1;
while(x < maxn)
if(mn[x<<1|1] < v)
x <<= 1, x |= 1;
else
x <<= 1;
// printf("find - %d %d\n", v, x-maxn);
return x - maxn;
}
} seg;
int back[maxn];
map<int,int> mp;
struct ST {
// vector<pair<int,int>> ans; // still brute
pair<int,int> ans;
void calc(int x, int y) {
int maior = seg.query(0, x-1);
if(maior > y)
// ans.push_back({x, maior});
ans = max(ans, {x, maior});
int pos = seg.find(y);
if(pos > x)
ans = max(ans, {pos, y});
// ans.push_back({pos, y});
}
void insert(int x, int y) { seg.upd(x, y); }
int get(int x, int y) {
int aq = -0x3f3f3f3f;
// for(auto [x2, y2] : ans)
auto [x2, y2] = ans;
if(back[x2] > x && y2 > y) aq = max(aq, back[x2]+y2);
return aq;
}
} st;
int main() {
int n; scanf("%d", &n);
for(int i = 0; i < n; i++) {
int x, y, z; scanf("%d %d %d", &x, &y, &z);
pt[i] = {x, y, z};
mp[x] = 0;
}
int coord = 0;
for(auto& it : mp)
it.second = ++coord, back[coord] = it.second;
sort(pt, pt+n);
int ans = -1;
for(int i = 0, j = 0; i < n; i = j) {
for(; j < n && pt[i].z == pt[j].z; j++)
ans = max(ans, st.get(pt[j].x, pt[j].y) + pt[j].z);
for(j = i; j < n && pt[i].z == pt[j].z; j++)
st.insert(mp[pt[j].x], pt[j].y);
for(j = i; j < n && pt[i].z == pt[j].z; j++)
st.calc(mp[pt[j].x], pt[j].y);
}
printf("%d\n", ans);
}
Compilation message
team.cpp: In function 'int main()':
team.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | int n; scanf("%d", &n);
| ~~~~~^~~~~~~~~~
team.cpp:73:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | int x, y, z; scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4436 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4436 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4436 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
