Submission #733581

#TimeUsernameProblemLanguageResultExecution timeMemory
733581PringFire (JOI20_ho_t5)C++14
0 / 100
114 ms38940 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' typedef pair<int, int> pii; const int MXN = 200005; int n, q, a[MXN], b[MXN], t[MXN], l[MXN], r[MXN], smg[MXN * 4]; int spt[20][MXN]; void BUILDSPT() { for (int i = 0; i < n; i++) spt[0][i] = a[i]; for (int i = 1; i < 20; i++) { for (int j = 0; j < n; j++) { if (j - (1 << i) < 0) spt[i][j] = spt[i - 1][j]; else spt[i][j] = max(spt[i - 1][j], spt[i - 1][j - (1 << (i - 1))]); } } } int query(int w, int r) { int lg = __lg(w); if (r - (w - (1 << lg)) < 0) return spt[lg][r]; return max(spt[lg][r - w + (1 << lg)], spt[lg][r]); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> q; for (int i = 0; i < n; i++) cin >> a[i]; BUILDSPT(); for (int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i]; // MONO(t[0] + 1); // build(0, 0, n); // for (int i = 0; i < n; i++) cout << query(0, 0, n, l[i] - 1, r[i]) << endl; for (int i = 0; i < n; i++) cout << query(t[i] + 1, r[i] - 1) << endl; 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...