#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define int long long
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 1e18;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int n, N;
int a[MAXN], b[MAXN], c[MAXN];
vector <ipii> vec;
vector <int> x, y, z;
struct seg {
int st[4*MAXN];
seg() { memset(st, -1, sizeof st); }
int que(int id, int l, int r, int x, int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return -INF;
return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
}
int upd(int id, int l, int r, int x, int y){
if(l==r && l==x) return st[id] = max(st[id], y);
if(r<x || x<l) return st[id];
return st[id] = max(upd(lf, l, md, x, y), upd(rg, md+1, r, x, y));
}
} A;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> N;
for(int i=1; i<=N; i++){
int x, y, z; cin >> x >> y >> z;
vec.pb({{x, y}, z});
}
vec.pb({{-1, -1}, -1});
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
n = vec.size()-1;
for(int i=1; i<=n; i++){
a[i] = vec[i].fi.fi;
b[i] = vec[i].fi.se;
c[i] = vec[i].se;
}
vec.clear();
// delete dobel
//coor compress
x.pb(-1); y.pb(-1); z.pb(-1);
for(int i=1; i<=n; i++){
x.pb(a[i]); y.pb(b[i]); z.pb(c[i]);
}
sort(x.begin(), x.end()); x.resize(unique(x.begin(), x.end()) - x.begin());
sort(y.begin(), y.end()); y.resize(unique(y.begin(), y.end()) - y.begin());
sort(z.begin(), z.end()); z.resize(unique(z.begin(), z.end()) - z.begin());
for(int i=1; i<=n; i++){
a[i] = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
b[i] = lower_bound(y.begin(), y.end(), b[i]) - y.begin();
c[i] = lower_bound(z.begin(), z.end(), c[i]) - z.begin();
vec.pb({{a[i], b[i]}, c[i]});
}
vec.pb({{-1, -1}, -1});
sort(vec.begin(), vec.end());
//for(auto in : vec) cout << in.fi.fi << ' '<<in.fi.se << ' ' <<in.se << " in\n";
int ans = -1, las = 0;
for(int i=1; i<=n; i++){
if(vec[i].fi.fi != vec[i-1].fi.fi){ // upd segtree pas A nya udh lebih gede, gk boleh ==
for(int j=las+1; j<=i-1; j++){
A.upd(1, 1, n, vec[j].fi.se, vec[j].se);
}
las = i-1;
}
//cout << las << '\n';
// x value di i
for(int j=1; j<=i-1; j++){
if(vec[i].fi.fi <= vec[j].fi.fi || vec[j].fi.se <= vec[i].fi.se) continue; // bj <= bi
// cari yg x ttp i, y nya j
int idx = A.que(1, 1, n, 1, vec[j].fi.se-1); // max buat z
if(idx < 0 || idx <= max(vec[i].se, vec[j].se)) continue;
//cout << i << ' '<< j << ' ' << idx << " idx\n";
int te = x[vec[i].fi.fi] + y[vec[j].fi.se] + z[idx];
//int te = vec[i].fi.fi + vec[j].fi.se + idx;
ans = max(ans, te);
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
2 ms |
14940 KB |
Output is correct |
12 |
Correct |
2 ms |
14940 KB |
Output is correct |
13 |
Correct |
2 ms |
14940 KB |
Output is correct |
14 |
Correct |
2 ms |
14940 KB |
Output is correct |
15 |
Correct |
2 ms |
14940 KB |
Output is correct |
16 |
Correct |
2 ms |
14968 KB |
Output is correct |
17 |
Correct |
2 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14936 KB |
Output is correct |
21 |
Correct |
2 ms |
14940 KB |
Output is correct |
22 |
Correct |
2 ms |
14940 KB |
Output is correct |
23 |
Correct |
2 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
2 ms |
14940 KB |
Output is correct |
12 |
Correct |
2 ms |
14940 KB |
Output is correct |
13 |
Correct |
2 ms |
14940 KB |
Output is correct |
14 |
Correct |
2 ms |
14940 KB |
Output is correct |
15 |
Correct |
2 ms |
14940 KB |
Output is correct |
16 |
Correct |
2 ms |
14968 KB |
Output is correct |
17 |
Correct |
2 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14936 KB |
Output is correct |
21 |
Correct |
2 ms |
14940 KB |
Output is correct |
22 |
Correct |
2 ms |
14940 KB |
Output is correct |
23 |
Correct |
2 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
233 ms |
15336 KB |
Output is correct |
27 |
Correct |
167 ms |
15320 KB |
Output is correct |
28 |
Correct |
141 ms |
15192 KB |
Output is correct |
29 |
Correct |
107 ms |
15204 KB |
Output is correct |
30 |
Correct |
73 ms |
15208 KB |
Output is correct |
31 |
Correct |
192 ms |
15396 KB |
Output is correct |
32 |
Correct |
116 ms |
15264 KB |
Output is correct |
33 |
Correct |
27 ms |
15192 KB |
Output is correct |
34 |
Correct |
12 ms |
15192 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
12 ms |
15448 KB |
Output is correct |
38 |
Correct |
12 ms |
15244 KB |
Output is correct |
39 |
Correct |
19 ms |
14988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
45 ms |
19132 KB |
Output is correct |
12 |
Correct |
27 ms |
17364 KB |
Output is correct |
13 |
Correct |
33 ms |
18628 KB |
Output is correct |
14 |
Correct |
34 ms |
20032 KB |
Output is correct |
15 |
Correct |
38 ms |
20920 KB |
Output is correct |
16 |
Correct |
39 ms |
20812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
45 ms |
19132 KB |
Output is correct |
12 |
Correct |
27 ms |
17364 KB |
Output is correct |
13 |
Correct |
33 ms |
18628 KB |
Output is correct |
14 |
Correct |
34 ms |
20032 KB |
Output is correct |
15 |
Correct |
38 ms |
20920 KB |
Output is correct |
16 |
Correct |
39 ms |
20812 KB |
Output is correct |
17 |
Correct |
2 ms |
14936 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
2 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
29 ms |
14940 KB |
Output is correct |
22 |
Correct |
422 ms |
20412 KB |
Output is correct |
23 |
Correct |
41 ms |
20396 KB |
Output is correct |
24 |
Correct |
30 ms |
18376 KB |
Output is correct |
25 |
Correct |
41 ms |
20168 KB |
Output is correct |
26 |
Correct |
44 ms |
19852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
45 ms |
19132 KB |
Output is correct |
12 |
Correct |
27 ms |
17364 KB |
Output is correct |
13 |
Correct |
33 ms |
18628 KB |
Output is correct |
14 |
Correct |
34 ms |
20032 KB |
Output is correct |
15 |
Correct |
38 ms |
20920 KB |
Output is correct |
16 |
Correct |
39 ms |
20812 KB |
Output is correct |
17 |
Correct |
2 ms |
14936 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
2 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
29 ms |
14940 KB |
Output is correct |
22 |
Correct |
422 ms |
20412 KB |
Output is correct |
23 |
Correct |
41 ms |
20396 KB |
Output is correct |
24 |
Correct |
30 ms |
18376 KB |
Output is correct |
25 |
Correct |
41 ms |
20168 KB |
Output is correct |
26 |
Correct |
44 ms |
19852 KB |
Output is correct |
27 |
Correct |
3 ms |
15024 KB |
Output is correct |
28 |
Correct |
3 ms |
14940 KB |
Output is correct |
29 |
Correct |
2 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14936 KB |
Output is correct |
31 |
Correct |
133 ms |
15196 KB |
Output is correct |
32 |
Correct |
3 ms |
14940 KB |
Output is correct |
33 |
Correct |
3 ms |
14940 KB |
Output is correct |
34 |
Execution timed out |
2081 ms |
27796 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
45 ms |
19132 KB |
Output is correct |
12 |
Correct |
27 ms |
17364 KB |
Output is correct |
13 |
Correct |
33 ms |
18628 KB |
Output is correct |
14 |
Correct |
34 ms |
20032 KB |
Output is correct |
15 |
Correct |
38 ms |
20920 KB |
Output is correct |
16 |
Correct |
39 ms |
20812 KB |
Output is correct |
17 |
Correct |
2 ms |
14936 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
2 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
29 ms |
14940 KB |
Output is correct |
22 |
Correct |
422 ms |
20412 KB |
Output is correct |
23 |
Correct |
41 ms |
20396 KB |
Output is correct |
24 |
Correct |
30 ms |
18376 KB |
Output is correct |
25 |
Correct |
41 ms |
20168 KB |
Output is correct |
26 |
Correct |
44 ms |
19852 KB |
Output is correct |
27 |
Correct |
3 ms |
15024 KB |
Output is correct |
28 |
Correct |
3 ms |
14940 KB |
Output is correct |
29 |
Correct |
2 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14936 KB |
Output is correct |
31 |
Correct |
133 ms |
15196 KB |
Output is correct |
32 |
Correct |
3 ms |
14940 KB |
Output is correct |
33 |
Correct |
3 ms |
14940 KB |
Output is correct |
34 |
Execution timed out |
2081 ms |
27796 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
2 ms |
14940 KB |
Output is correct |
12 |
Correct |
2 ms |
14940 KB |
Output is correct |
13 |
Correct |
2 ms |
14940 KB |
Output is correct |
14 |
Correct |
2 ms |
14940 KB |
Output is correct |
15 |
Correct |
2 ms |
14940 KB |
Output is correct |
16 |
Correct |
2 ms |
14968 KB |
Output is correct |
17 |
Correct |
2 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14936 KB |
Output is correct |
21 |
Correct |
2 ms |
14940 KB |
Output is correct |
22 |
Correct |
2 ms |
14940 KB |
Output is correct |
23 |
Correct |
2 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
233 ms |
15336 KB |
Output is correct |
27 |
Correct |
167 ms |
15320 KB |
Output is correct |
28 |
Correct |
141 ms |
15192 KB |
Output is correct |
29 |
Correct |
107 ms |
15204 KB |
Output is correct |
30 |
Correct |
73 ms |
15208 KB |
Output is correct |
31 |
Correct |
192 ms |
15396 KB |
Output is correct |
32 |
Correct |
116 ms |
15264 KB |
Output is correct |
33 |
Correct |
27 ms |
15192 KB |
Output is correct |
34 |
Correct |
12 ms |
15192 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
12 ms |
15448 KB |
Output is correct |
38 |
Correct |
12 ms |
15244 KB |
Output is correct |
39 |
Correct |
19 ms |
14988 KB |
Output is correct |
40 |
Correct |
2 ms |
14940 KB |
Output is correct |
41 |
Correct |
2 ms |
14940 KB |
Output is correct |
42 |
Correct |
2 ms |
14940 KB |
Output is correct |
43 |
Correct |
2 ms |
14940 KB |
Output is correct |
44 |
Correct |
2 ms |
14940 KB |
Output is correct |
45 |
Correct |
2 ms |
14940 KB |
Output is correct |
46 |
Correct |
2 ms |
14940 KB |
Output is correct |
47 |
Correct |
2 ms |
14940 KB |
Output is correct |
48 |
Correct |
2 ms |
14940 KB |
Output is correct |
49 |
Correct |
2 ms |
14940 KB |
Output is correct |
50 |
Correct |
45 ms |
19132 KB |
Output is correct |
51 |
Correct |
27 ms |
17364 KB |
Output is correct |
52 |
Correct |
33 ms |
18628 KB |
Output is correct |
53 |
Correct |
34 ms |
20032 KB |
Output is correct |
54 |
Correct |
38 ms |
20920 KB |
Output is correct |
55 |
Correct |
39 ms |
20812 KB |
Output is correct |
56 |
Correct |
2 ms |
14936 KB |
Output is correct |
57 |
Correct |
3 ms |
14940 KB |
Output is correct |
58 |
Correct |
2 ms |
14940 KB |
Output is correct |
59 |
Correct |
3 ms |
14940 KB |
Output is correct |
60 |
Correct |
29 ms |
14940 KB |
Output is correct |
61 |
Correct |
422 ms |
20412 KB |
Output is correct |
62 |
Correct |
41 ms |
20396 KB |
Output is correct |
63 |
Correct |
30 ms |
18376 KB |
Output is correct |
64 |
Correct |
41 ms |
20168 KB |
Output is correct |
65 |
Correct |
44 ms |
19852 KB |
Output is correct |
66 |
Correct |
3 ms |
15024 KB |
Output is correct |
67 |
Correct |
3 ms |
14940 KB |
Output is correct |
68 |
Correct |
2 ms |
14940 KB |
Output is correct |
69 |
Correct |
3 ms |
14936 KB |
Output is correct |
70 |
Correct |
133 ms |
15196 KB |
Output is correct |
71 |
Correct |
3 ms |
14940 KB |
Output is correct |
72 |
Correct |
3 ms |
14940 KB |
Output is correct |
73 |
Execution timed out |
2081 ms |
27796 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |