Submission #885695

#TimeUsernameProblemLanguageResultExecution timeMemory
885695ByeWorldTeam Contest (JOI22_team)C++14
0 / 100
32 ms19260 KiB
#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 // 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()); //cout << A.que(1, 1,n, 1, 1) << '\n'; //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){ for(int j=las+1; j<=i-1; j++){ A.upd(1, 1, n, vec[j].fi.se, vec[j].se); } las = i-1; } 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 int idx = A.que(1, 1, n, 1, vec[j].fi.se-1); 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 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...