Submission #1166865

#TimeUsernameProblemLanguageResultExecution timeMemory
1166865chikien2009Team Contest (JOI22_team)C++20
46 / 100
393 ms17992 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); } } st(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) { st.Update(a[j].Y, a[j].Z); j++; } x = -1; l = a[i].Y + 1; r = 450000; while (l <= r) { e = (l + r) >> 1; c = max(a[i].Z, st.GetMin(e, 450000)); d = st.GetMax(1, e - 1); if (c == 1e9) { r = e - 1; continue; } else if (d == -1e9) { l = e + 1; continue; } if (c < d) { l = e + 1; x = e; } else { r = e - 1; } } if (x == -1) { continue; } res = max(res, b[a[i].X - 1] + b[x - 1] + b[st.GetMax(1, x - 1) - 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...