제출 #558385

#제출 시각아이디문제언어결과실행 시간메모리
558385fatemetmhr유괴 2 (JOI17_abduction2)C++17
100 / 100
1689 ms10024 KiB
// Be name khoda // #include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(x) x.begin(), x.end() #define fi first #define se second #define pb push_back const int maxn5 = 1e5 + 10; const int maxnt = 4e5 + 10; struct segment_tree{ int val[maxn5]; int mx[maxnt]; inline void build(int l, int r, int v){ if(r - l == 1){ mx[v] = val[l]; return; } int mid = (l + r) >> 1; build(l, mid, v * 2); build(mid, r, v * 2 + 1); mx[v] = max(mx[v * 2], mx[v * 2 + 1]); } inline int get_first(int l, int r, int lq, int rq, int val, int v){ if(rq <= l || r <= lq || mx[v] <= val) return -1; if(r - l == 1) return l; int mid = (l + r) >> 1; int ans = get_first(l, mid, lq, rq, val, v * 2); if(ans != -1) return ans; return get_first(mid, r, lq, rq, val, v * 2 + 1); } inline int get_last(int l, int r, int lq, int rq, int val, int v){ if(rq <= l || r <= lq || mx[v] <= val) return -1; if(r - l == 1) return l; int mid = (l + r) >> 1; int ans = get_last(mid, r, lq, rq, val, v * 2 + 1); if(ans != -1) return ans; return get_last(l, mid, lq, rq, val, v * 2); } } seg1, seg2; int a[maxn5], b[maxn5], pt1[2][maxn5], pt2[2][maxn5]; int up[maxn5], dw[maxn5], lef[maxn5], rig[maxn5]; vector <pair<pair<int, int>, bool>> av; ll ans[2][2][maxn5], n, m, x, y; inline ll setmn(ll a, ll b){ if(a == -1) return b; if(b == -1) return a; return min(a, b); } inline ll setmx(ll a, ll b){ if(a == -1) return b; if(b == -1) return a; return max(a, b); } inline ll solve(bool exty){ //cout << "satring with solve " << endl; for(auto [p, ty] : av){ int id = p.se; if(ty && up[id] == -1) continue; if(!ty && lef[id] == -1) continue; if(ty){ // stoon int pt = seg1.get_last(0, n, 0, up[id] + 1, b[id], 1); if(pt != -1){ lef[pt] = setmn(lef[pt], id); rig[pt] = setmx(rig[pt], id); } else{ ans[ty][0][id] = up[id]; } pt1[ty][id] = pt; pt = seg1.get_first(0, n, dw[id], n, b[id], 1); if(pt != -1){ lef[pt] = setmn(lef[pt], id); rig[pt] = setmx(rig[pt], id); } else{ ans[ty][1][id] = n - dw[id] - 1; } pt2[ty][id] = pt; } else{ // satr int pt = seg2.get_last(0, m, 0, lef[id] + 1, a[id], 1); if(pt != -1){ dw[pt] = setmx(dw[pt], id); up[pt] = setmn(up[pt], id); } else{ ans[ty][0][id] = lef[id]; } pt1[ty][id] = pt; pt = seg2.get_first(0, m, rig[id], m, a[id], 1); if(pt != -1){ dw[pt] = setmx(dw[pt], id); up[pt] = setmn(up[pt], id); } else{ ans[ty][1][id] = m - rig[id] - 1; } pt2[ty][id] = pt; } //cout << ty << ' ' << id << ' ' << lef[id] << ' ' << rig[id] << ' ' << up[id] << ' ' << dw[id] << endl; //cout << "edame " << pt1[ty][id] << ' ' << pt2[ty][id] << ' ' << ans[ty][0][id] << ' ' << ans[ty][1][id] << endl; } reverse(all(av)); for(auto [p, ty] : av){ int id = p.se; if(ty && up[id] == -1) continue; if(!ty && lef[id] == -1) continue; int pt = pt1[ty][id]; if(pt1[ty][id] != -1){ if(ty){ ans[ty][0][id] = max(ans[ty ^ 1][0][pt] + id - lef[pt], ans[ty ^ 1][1][pt] + rig[pt] - id) + up[id] - pt; } else{ ans[ty][0][id] = max(ans[ty ^ 1][0][pt] + id - up[pt], ans[ty ^ 1][1][pt] + dw[pt] - id) + lef[id] - pt; } } pt = pt2[ty][id]; if(pt != -1){ if(ty){ ans[ty][1][id] = max(ans[ty ^ 1][0][pt] + id - lef[pt], ans[ty ^ 1][1][pt] + rig[pt] - id) + pt - dw[id]; } else{ ans[ty][1][id] = max(ans[ty ^ 1][0][pt] + id - up[pt], ans[ty ^ 1][1][pt] + dw[pt] - id) + pt - rig[id]; } } //cout << "ans of " << ty << ' '<< id << ' ' << ans[ty][0][id] << ' ' << ans[ty][1][id] << endl; } //cout << max({ans[0][0][x], ans[0][1][x], ans[1][0][y], ans[1][1][y]}) << '\n'; reverse(all(av)); if(exty){ ans[1][0][y] = ans[1][1][y] = (up[y] < x ? ans[1][0][y] : ans[1][1][y]); return max({ans[0][0][x], ans[0][1][x], ans[1][0][y] + 1, ans[1][1][y] + 1}); } else{ ans[0][0][x] = ans[0][1][x] = (lef[x] > y ? ans[0][1][x] : ans[0][0][x]); return max({ans[0][0][x] + 1, ans[0][1][x] + 1, ans[1][0][y], ans[1][1][y]}); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q; cin >> n >> m >> q; for(int i = 0; i < n; i++){ cin >> a[i]; seg1.val[i] = a[i]; av.pb({{a[i], i}, 0}); } for(int i = 0; i < m; i++){ cin >> b[i]; seg2.val[i] = b[i]; av.pb({{b[i], i}, 1}); } sort(all(av)); seg1.build(0, n, 1); seg2.build(0, m, 1); for(int i = 0; i < q; i++){ cin >> x >> y; x--; y--; ll anss = 0; if(a[x] > b[y]){ memset(lef, -1, sizeof lef); memset(rig, -1, sizeof rig); memset(up, -1, sizeof up); memset(dw, -1, sizeof dw); memset(ans, 0, sizeof ans); lef[x] = rig[x] = y; up[y] = dw[y] = x - 1; if(x > 0) anss = max(anss, solve(true)); memset(lef, -1, sizeof lef); memset(rig, -1, sizeof rig); memset(up, -1, sizeof up); memset(dw, -1, sizeof dw); memset(ans, 0, sizeof ans); lef[x] = rig[x] = y; up[y] = dw[y] = x + 1; if(x + 1 < n) anss = max(anss, solve(true)); } else{ memset(lef, -1, sizeof lef); memset(rig, -1, sizeof rig); memset(up, -1, sizeof up); memset(dw, -1, sizeof dw); memset(ans, 0, sizeof ans); up[y] = dw[y] = x; lef[x] = rig[x] = y - 1; if(y > 0) anss = max(anss, solve(false)); memset(lef, -1, sizeof lef); memset(rig, -1, sizeof rig); memset(up, -1, sizeof up); memset(dw, -1, sizeof dw); memset(ans, 0, sizeof ans); up[y] = dw[y] = x; lef[x] = rig[x] = y + 1; if(y + 1 < m) anss = max(anss, solve(false)); } cout << anss << '\n'; } } /* 3 3 1 3 2 6 1 4 5 3 3 */
#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...