Submission #883853

#TimeUsernameProblemLanguageResultExecution timeMemory
883853serifefedartarHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
3097 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9 + 9; const ll LOGN = 21; const ll MAXN = 1e6 + 100; vector<int> w, mst[4*MAXN]; int ans[4*MAXN]; void merge(int k, int a, int b) { vector<int> A = mst[2*k]; vector<int> B = mst[2*k+1]; reverse(A.begin(), A.end()); reverse(B.begin(), B.end()); int mx_B = -2e9; while (A.size() || B.size()) { int valA = (A.size() ? A.back() : 2e9); int valB = (B.size() ? B.back() : 2e9); if (valA < valB) { mst[k].push_back(valA); ans[k] = max(ans[k], valA + mx_B); A.pop_back(); } else { mst[k].push_back(valB); mx_B = max(mx_B, valB); B.pop_back(); } } } void init(int k, int a, int b) { if (a == b) { ans[k] = 0; mst[k].push_back(w[a]); return ; } init(2*k, a, (a+b)/2); init(2*k+1, (a+b)/2+1, b); merge(k, a, b); } pair<int,int> query(int k, int a, int b, int q_l, int q_r, int mx) { if (b < q_l || a > q_r) return {-2e9, -2e9}; if (q_l <= a && b <= q_r) { auto lb = lower_bound(mst[k].begin(), mst[k].end(), mx); if (lb == mst[k].begin()) return {mst[k].back(), ans[k]}; return {mst[k].back(), max(ans[k], mx + *prev(lb))}; } pair<int,int> Q1 = query(2*k, a, (a+b)/2, q_l, q_r, mx); pair<int,int> Q2 = query(2*k+1, (a+b)/2+1, b, q_l, q_r, Q1.f); pair<int,int> new_p = {max(Q1.f, Q2.f), max(Q1.s, Q2.s)}; return new_p; } int main() { fast int N, M; cin >> N >> M; w = vector<int>(N+1); for (int i = 1; i <= N; i++) cin >> w[i]; init(1, 1, N); for (int i = 0; i < M; i++) { int l, r, k; cin >> l >> r >> k; int Q = query(1, 1, N, l, r, 0).s; if (Q > k) cout << "0\n"; else cout << "1\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...