제출 #892218

#제출 시각아이디문제언어결과실행 시간메모리
892218vjudge1Team Contest (JOI22_team)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define size(x) (int)x.size() template<class S, class T> bool chmin(S &a, const T &b) { return a > b && (a = b) == b; } template<class S, class T> bool chmax(S &a, const T &b) { return a < b && (a = b) == b; } const int inf = 1e9 + 7; const int INF = 1e18 + 7; const int mod = 998244353; map<int, int> mp; struct Fenwick { int n; vector<int> t; Fenwick(int n) { this->n = n; t.assign(n, -1); } void upd(int i, int x) { for (; i < n; i = i | (i + 1)) { chmax(t[i], x); } } int get(int i) { int res = -1; for (; i >= 0; i = (i & (i + 1)) - 1) { chmax(res, t[i]); } return res; } }; signed main() { cin.tie(nullptr)->sync_with_stdio(false); int n, res = -1, Max = -1; cin >> n; vector<array<int, 3>> v(n); for (int i = 0; i < n; ++i) { cin >> v[i][0] >> v[i][1] >> v[i][2]; } sort(all(v)); vector<int> compress; for (int i = 0; i < n; ++i) { if (!mp.count(v[i][1])) { compress.push_back(v[i][1]); mp[v[i][1]]; } if (!mp.count(v[i][2])) { compress.push_back(v[i][2]); mp[v[i][2]]; } } sort(all(compress)); for (int i = 0; i < size(compress); ++i) { mp[compress[i]] = i; } Fenwick y(size(compress)), z(size(compress)); for (int i = 0; i < n; ++i) { int j; for (j = i; j < n && v[i][0] == v[j][0]; j++) { if (Max != -1) { chmax(res, Max + v[j][0]); } } for (j = i; j < n && v[i][0] == v[j][0]; j++) { int Find = y.get(mp[v[j][2]] - 1); if (Find != -1) { chmax(Max, v[j][2] + Find); } Find = z.get(mp[v[j][1]] - 1); if (Find != -1) { chmax(Max, v[j][1] + Find); } y.upd(mp[v[j][2]], v[j][1]); z.upd(mp[v[j][1]], v[j][2]); } i = j - 1; } cout << res; }
#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...