#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 1;
const int M = 5E5 + 1;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
int n;
int a[N], b[N], c[N];
int sa[N], sb[N], sc[N];
struct node {
node *l = nullptr, *r = nullptr;
int val = 0;
} *Brt = new node(), *Crt = new node();
struct tdnode {
tdnode *l = nullptr, *r = nullptr;
node *val = nullptr;
tdnode() {
val = new node();
}
} *tdrt = new tdnode();
vector<ll> scan[M];
void upd(int p, int z, node *v, int tl = 0, int tr = M + 1) {
if(tl == tr) {
v->val = max(v->val, z);
return;
}
ll m = (tl + tr) >> 1ll;
if(p <= m) {
if(!v->l)v->l = new node();
upd(p, z, v->l, tl, m);
} else {
if(!v->r)v->r = new node();
upd(p, z, v->r, m + 1, tr);
}
v->val = max(v->val, z);
}
int get(int l, int r, node *v, int tl = 0, int tr = M + 1) {
if(l > tr || tl > r || !v)
return 0;
if(l <= tl && tr <= r)
return v->val;
ll m = (tl + tr) >> 1ll;
return max(get(l, r, v->l, tl, m), get(l, r, v->r, m + 1, tr));
}
void upd2(int x, int y, int z, tdnode *v, int tl = 0, int tr = M + 1) {
if(tl == tr) {
upd(y, z, v->val);
return;
}
ll m = (tl + tr) >> 1ll;
if(x <= m) {
if(!v->l)v->l = new tdnode();
upd2(x, y, z, v->l, tl, m);
} else {
if(!v->r)v->r = new tdnode();
upd2(x, y, z, v->r, m + 1, tr);
}
upd(y, z, v->val);
}
int get2(int lx, int rx, int ly, int ry, tdnode *v, int tl = 0, int tr = M + 1) {
if(lx > tr || rx < tl || !v)return 0;
if(lx <= tl && tr <= rx) {
return get(ly, ry, v->val);
}
ll m = (tl + tr) >> 1ll;
return max(get2(lx, rx, ly, ry, v->l, tl , m), get2(lx, rx, ly, ry, v->r, m + 1, tr));
}
bool comp2(int i, int j) {
return b[i] < b[j];
}
bool comp1(int i, int j) {
return c[i] < c[j];
}
int main() {
speed;
cin >> n;
vector<int> g, g2, g3;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
g.pb(a[i]);
g2.pb(b[i]);
g3.pb(c[i]);
}
sort(g.begin(), g.end());
g.erase(unique(g.begin(), g.end()), g.end());
sort(g2.begin(), g2.end());
g2.erase(unique(g2.begin(), g2.end()), g2.end());
sort(g3.begin(), g3.end());
g3.erase(unique(g3.begin(), g3.end()), g3.end());
for(int j = 1; j <= n; j++) {
sa[j] = lower_bound(g.begin(), g.end(), a[j]) - g.begin() + 1;
sb[j] = lower_bound(g2.begin(), g2.end(), b[j]) - g3.begin() + 1;
sc[j] = lower_bound(g3.begin(), g3.end(), c[j]) - g3.begin() + 1;
scan[sa[j]].pb(j);
}
int sum = -1;
for(int i = 1; i <= g.size(); i++) {
for(auto u : scan[i]) {
int z = get2(sb[u] + 1, M, sc[u] + 1, M, tdrt);
if(z)sum = max(sum, a[u] + z);
}
sort(scan[i].begin(), scan[i].end(), comp1);
for(auto u : scan[i]) {
upd(sc[u], sb[u], Crt);
int gt2 = get(0, sc[u] - 1, Crt);
if(gt2 > sb[u]) {
upd2(gt2, sc[u], c[u] + g2[gt2 - 1], tdrt);
}
}
sort(scan[i].begin(), scan[i].end(), comp2);
for(auto u : scan[i]) {
upd(sb[u], sc[u], Brt);
int gt = get(0, sb[u] - 1, Brt);
if(gt > sc[u]) {
upd2(sb[u], gt, b[u] + g3[gt - 1], tdrt);
}
}
}
cout << sum;
}
Compilation message
team.cpp: In function 'int main()':
team.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 1; i <= g.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
