제출 #1208049

#제출 시각아이디문제언어결과실행 시간메모리
1208049AndreyTeam Contest (JOI22_team)C++20
0 / 100
89 ms14004 KiB
#include<bits/stdc++.h> using namespace std; vector<int> x(200001); vector<int> y(200001); vector<int> z(200001); vector<int> seg(1000001,INT_MAX); vector<int> big(1000001,-1); void upd(int l, int r, int x, int p, int c) { if(l == r) { seg[x] = c; big[x] = c; return; } int mid = (l+r)/2; if(p <= mid) { upd(l,mid,x*2,p,c); } else { upd(mid+1,r,x*2+1,p,c); } seg[x] = min(seg[x*2],seg[x*2+1]); big[x] = max(big[x*2],big[x*2+1]); } int calc1(int l, int r, int x, int d) { if(l == r) { if(seg[x] < d) { return l; } else { return l+1; } } int mid = (l+r)/2; if(seg[x*2] < d) { return calc1(l,mid,x*2,d); } else { return calc1(mid+1,r,x*2+1,d); } } int calc2(int l, int r, int x, int d) { if(l == r) { if(big[x] > d) { return l; } else { return l-1; } } int mid = (l+r)/2; if(big[x*2+1] > d) { return calc2(mid+1,r,x*2+1,d); } else { return calc2(l,mid,x*2,d); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector<pair<pair<int,int>,int>> idk(0); for(int i = 0; i < n; i++) { cin >> x[i] >> y[i] >> z[i]; idk.push_back({{x[i],y[i]},i}); } sort(idk.begin(),idk.end()); reverse(idk.begin(),idk.end()); vector<int> pos(n); for(int i = 0; i < n; i++) { pos[idk[i].second] = i; } int ans = -1,mx = -1,my = -1; int p = n; vector<pair<int,int>> banana(n); for(int i = 0; i < n; i++) { banana[i] = {z[i],i}; } sort(banana.begin(),banana.end()); int w = 0; vector<bool> yeah(n); while(w < n) { int r = n-1; for(int i = w; i < n; i++) { if(banana[i].first != banana[w].first) { r = i-1; break; } } for(int i = w; i <= r; i++) { int c = banana[i].second; if(x[c] < mx && y[c] < my) { ans = max(ans,mx+my+z[c]); } } for(int i = w; i <= r; i++) { int c = banana[i].second; yeah[pos[c]] = true; int l = n; if(calc1(0,n-1,1,y[c]) < pos[c]) { l = calc1(0,n-1,1,y[c]); } if(calc2(0,n-1,1,y[c]) > pos[c]) { l = min(l,pos[c]); } while(p > l) { p--; if(yeah[p]) { mx = max(mx,x[p]); my = max(my,y[p]); } } upd(0,n-1,1,pos[c],y[c]); if(c >= p) { mx = max(mx,x[c]); my = max(my,y[c]); } } w = r+1; } cout << ans; 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...