Submission #1020963

#TimeUsernameProblemLanguageResultExecution timeMemory
1020963vjudge3Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
858 ms75160 KiB
#include <bits/stdc++.h> using namespace std; int a[1000005]; bool ans[1000005]; const int inf = 1e9; struct Node { int ans, mx; } seg[4000005]; struct Query { int id, l, r, k; bool operator< (Query& o) {return r < o.r;} }; int query_idx(int id, int l, int r, int x) { if (l == r) return l; if (seg[id*2+1].mx > x) return query_idx(id*2+1, (l+r)/2+1, r, x); return query_idx(id*2, l, (l+r)/2, x); } void upd_ans(int id, int l, int r, int pos, int x) { if (l == r) { seg[id].ans = max(seg[id].ans, x); return; } int mid = (l+r)/2; if (mid < pos) upd_ans(id*2+1, mid+1, r, pos, x); else upd_ans(id*2, l, mid, pos, x); seg[id].ans = max(seg[id*2].ans, seg[id*2+1].ans); } void upd_mx(int id, int l, int r, int pos, int x) { if (l == r) { seg[id].mx = x; return; } int mid = (l+r)/2; if (mid < pos) upd_mx(id*2+1, mid+1, r, pos, x); else upd_mx(id*2, l, mid, pos, x); seg[id].mx = max(seg[id*2].mx, seg[id*2+1].mx); } int query_ans(int id, int l, int r, int ql) { if (r < ql) return 0; if (ql <= l) return seg[id].ans; return max(query_ans(id*2, l, (l+r)/2, ql), query_ans(id*2+1, (l+r)/2+1, r, ql)); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; vector<Query> query (m); for (int i = 0; i < m; i++) { query[i].id = i+1; cin >> query[i].l >> query[i].r >> query[i].k; } query.push_back({0, 0, 0, 0}); sort(query.begin(), query.end()); for (int i = 1; i <= m; i++) { for (int j = query[i-1].r+1; j <= query[i].r; j++) { upd_mx(1, 1, n, j, a[j]); if (seg[1].mx != a[j]) { int idx = query_idx(1, 1, n, a[j]); upd_ans(1, 1, n, idx, a[idx] + a[j]); } } ans[query[i].id] = query_ans(1, 1, n, query[i].l) <= query[i].k; } for (int i = 1; i <= m; i++) cout << ans[i] << '\n'; 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...