#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;
void dbg(){
cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
cerr << h << ", ";
dbg(t...);
}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
#else
#define er(...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 5e5 + 5, lg = 21, inf = ll(1e9) + 5;
struct Fen{
vector<int> fen;
Fen(){}
Fen(int n){
fen.assign(n + 1, -inf);
}
void upd(int i, int k){
for(i++; i < sz(fen); i += i&-i) fen[i] = max(fen[i], k);
}
int get(int i){
int res = -inf;
for(i++; i; i -= i&-i) res = max(res, fen[i]);
return res;
}
} prf, suf;
int n, x[maxn], y[maxn], z[maxn];
int X = -1, Y = -1, id;
map<int, int> mp;
multiset<pp> s;
void add(int x, int y){
er(x, y);
// for(auto[x, y]: s){
// er(x, y);
// }
vector<pp> del;
auto it = s.lower_bound(pp(x, -1));
while(it != begin(s)){
it--;
if(it->ss <= y) break;
del.pb(*it);
}
auto it2 = s.upper_bound(pp(x, inf));
while(it2 != end(s)){
if(it2->ss >= y) break;
del.pb(*it2);
it2++;
}
auto add2 = [&](int x, int y){
er(x, y);
X = max(X, x), Y = max(Y, y);
prf.upd(mp[x], y);
suf.upd(id-mp[x]-1, -y);
};
if(del.empty()){
if(prf.get(mp[x]-1) > y) add2(x, y);
else {
if(-suf.get(id-1-mp[x]-1) < y) add2(x, y);
else s.insert({x, y});
}
} else{
add2(x, y);
for(auto p: del){
// er(p.ff, p.ss);
auto it = s.find(p);
add2(p.ff, p.ss);
s.erase(it);
}
}
}
int slv1(){
s.clear(), X = Y = -1, mp.clear();
map<int, vector<pp>> mpp;
rep(i,0,n){
mpp[z[i]].pb({x[i], y[i]});
mp[x[i]] = 0;
}
for(auto&c: mp) c.ss = id++;
prf = Fen(id);
suf = Fen(id);
int ans = -1;
for(auto[Z, v]: mpp){
for(auto[x, y]: v){
if(X > x && Y > y){
ans = max(ans, Z + X + Y);
}
}
for(auto[x, y]: v){
add(x, y);
}
}
return ans;
}
int main(){ IOS();
cin >> n;
rep(i,0,n){
cin >> x[i] >> y[i] >> z[i];
}
cout << slv1() << '\n';
return 0;
}
Compilation message
team.cpp: In function 'void IOS()':
team.cpp:24:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen("inp.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
team.cpp:25:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
