Submission #561586

#TimeUsernameProblemLanguageResultExecution timeMemory
561586fatemetmhrTeam Contest (JOI22_team)C++17
0 / 100
9 ms19924 KiB
// Be name khoda // #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define all(x) x.begin(), x.end() #define fi first #define se second const int maxn5 = 2e5 + 10; const int maxnt = 8e5 + 10; const ll inf = 1e18; int n; struct segment_tree_bs{ ll mx[maxnt]; int get_first(int l, int r, int lq, int rq, ll val, int v){ if(rq <= l || r <= lq || mx[v] <= val) return n; if(r - l == 1) return l; int mid = (l + r) >> 1; int ans = get_first(l, mid, lq, rq, val, v * 2); if(ans != n) return ans; return get_first(mid, r, lq, rq, val, v * 2 + 1); } ll get_max(int l, int r, int lq, int rq, int v){ if(rq <= l || r <= lq) return -inf; if(lq <= l && r <= rq) return mx[v]; int mid = (l + r) >> 1; return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1)); } void update(int l, int r, int id, ll val, int v){ if(r - l == 1){ mx[v] = val; return; } int mid = (l + r) >> 1; if(id < mid) update(l, mid, id, val, v * 2); else update(mid, r, id, val, v * 2 + 1); mx[v] = max(mx[v * 2], mx[v * 2 + 1]); return; } } val3_stored; struct segment_tree_val2_plus_mx_val3{ ll mxval2[maxnt], mxval3[maxnt], mx[maxnt]; bool newval[maxnt]; void build(){ fill(mxval2, mxval2 + maxnt, -inf); fill(mxval3, mxval3 + maxnt, -inf); fill(mx, mx + maxnt, -inf); memset(newval, false, sizeof newval); return; } void shift(int v){ if(!newval[v]) return; newval[v] = false; mxval3[v * 2] = mxval3[v * 2 + 1] = mxval3[v]; newval[v * 2] = newval[v * 2 + 1] = true; mx[v * 2] = mxval2[v * 2] + mxval3[v]; mx[v * 2 + 1] = mxval2[v * 2 + 1] + mxval3[v]; return; } void update_doone(int l, int r, int id, ll val, int v){ if(r - l == 1){ mxval2[v] = val; mx[v] = val + mxval3[v]; return; } int mid = (l + r) >> 1; shift(v); if(id < mid) update_doone(l, mid, id, val, v * 2); else update_doone(mid, r, id, val, v * 2 + 1); mxval2[v] = max(mxval2[v * 2], mxval2[v * 2 + 1]); mx[v] = max(mx[v * 2], mx[v * 2 + 1]); } void sset(int l, int r, int lq, int rq, ll val, int v){ if(rq <= l || r <= lq) return; if(lq <= l && r <= rq){ newval[v] = true; mxval3[v] = val; mx[v] = val + mxval2[v]; return; } int mid = (l + r) >> 1; shift(v); sset(l, mid, lq, rq, val, v * 2); sset(mid, r, lq, rq, val, v * 2 + 1); mx[v] = mx[v * 2] + mx[v * 2 + 1]; return; } ll get_max(int l, int r, int lq, int rq, int v){ if(rq <= l || r <= lq) return -inf; if(lq <= l && r <= rq) return mx[v]; int mid = (l + r) >> 1; shift(v); return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1)); } } main_seg; int pos2[maxn5], per1[maxn5], per2[maxn5]; ll bsval2[maxn5], val1[maxn5], val2[maxn5], val3[maxn5]; vector <int> toadd; bool cmp1(int i, int j){return val1[i] < val1[j];} bool cmp2(int i, int j){return val2[i] < val2[j];} inline void add(int v){ main_seg.update_doone(0, n, pos2[v], val2[v], 1); if(val3_stored.get_max(0, n, 0, pos2[v], 1) <= val3[v]){ int last = val3_stored.get_first(0, n, pos2[v], n, val3[v] - 1, 1); main_seg.sset(0, n, pos2[v] + 1, last, val3[v], 1); main_seg.sset(0, n, pos2[v], pos2[v] + 1, -inf, 1); } val3_stored.update(0, n, pos2[v], val3[v], 1); return; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; i++){ cin >> val1[i] >> val2[i] >> val3[i]; per1[i] = per2[i] = i; } sort(per1, per1 + n, cmp1); // bar hasbe val1 sort(per2, per2 + n, cmp2); // bar hasbe val2 for(int i = 0; i < n; i++){ pos2[per2[i]] = i; bsval2[i] = val2[per2[i]]; } main_seg.build(); // hame ro bezar -inf // val3_stored.build(0, n, 1); // hame ro bezar 0 ll ans = -1; for(int i = 0; i < n; i++){ int v = per1[i]; while(toadd.size() && val1[toadd.back()] < val1[v]){ add(toadd.back()); toadd.pop_back(); } int pt1 = upper_bound(bsval2, bsval2 + n, val2[v]) - bsval2; int pt2 = val3_stored.get_first(0, n, 0, n, val3[v], 1); // avalin kasi ke az akidan val3 bishtar darad, agar nabood n midahad int pt = max(pt1, pt2); ans = max(ans, main_seg.get_max(0, n, pt, n, 1) + val1[v]); toadd.pb(v); } cout << ans << endl; }
#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...