Submission #155486

#TimeUsernameProblemLanguageResultExecution timeMemory
155486qkxwsmHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
30 / 100
621 ms26204 KiB
#include <bits/stdc++.h> using namespace std; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) #define SZ(x) ((int) ((x).size())) #define ALL(x) (x).begin(), (x).end() #define MAXN 1000013 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; typedef pair<pii, pii> ppp; int N, Q; int arr[MAXN]; int rt[MAXN]; int sparse[20][MAXN]; vector<ppp> queries; bitset<MAXN> ans; //max (a[i] + a[j]) such that a[i] > a[j] int query(int l, int r) { int sz = 31 - __builtin_clz(r - l + 1); return max(sparse[sz][l], sparse[sz][r - (1 << sz) + 1]); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> Q; int mxv = 0; FOR(i, 0, N) { cin >> arr[i]; } FOR(i, 0, Q) { int l, r, v; cin >> l >> r >> v; l--; r--; ckmax(mxv, v); queries.PB({{l, r}, {v, i}}); } if (N <= 5000) { //subtask 1, 2 FOR(i, 0, N) { sparse[0][i] = arr[i]; } FOR(i, 1, 20) { FOR(j, 0, N - (1 << i)) { sparse[i][j] = max(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]); } } FOR(i, 0, Q) { int l = queries[i].fi.fi, r = queries[i].fi.se, v = queries[i].se.fi, qid = queries[i].se.se; FOR(j, l + 1, r + 1) { int mx = query(l, j - 1); if (mx > arr[j] && mx + arr[j] > v) { ans[qid] = true; break; } } } } else if (mxv <= 1013) { //subtask 4 } else { //subtask 3 //you just need to figure out if it's <= here or not. rt[N - 1] = N - 1; FORD(i, N - 1, 0) { rt[i] = (arr[i + 1] < arr[i] ? i : rt[i + 1]); } FOR(i, 0, Q) { int l = queries[i].fi.fi, r = queries[i].fi.se, v = queries[i].se.fi, qid = queries[i].se.se; ans[qid] = (rt[l] < r); } } //left, right, value, qid; FOR(i, 0, Q) { cout << (ans[i] ? 0 : 1) << '\n'; } }

Compilation message (stderr)

sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:110:52: warning: unused variable 'v' [-Wunused-variable]
    int l = queries[i].fi.fi, r = queries[i].fi.se, v = queries[i].se.fi, qid = queries[i].se.se;
                                                    ^
#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...