Submission #1166992

#TimeUsernameProblemLanguageResultExecution timeMemory
1166992chikien2009Team Contest (JOI22_team)C++20
100 / 100
884 ms32072 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...