Submission #170251

#TimeUsernameProblemLanguageResultExecution timeMemory
170251LightningHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
1430 ms87288 KiB
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <stack> #include <queue> #include <deque> using namespace std; typedef long long ll; typedef pair <int, int> pii; #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define show(a) cerr << #a <<" -> "<< a <<"\n" #define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d)) #define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d)) //#define int ll const int szT = (1 << 20) - 1; const int INF = 1e9 + 5; int n, m, a[szT], t[szT * 3]; vector <pair <int, pii> > que[szT]; stack <int> st; bool ans[szT]; void upd(int pos, int x) { pos += szT; t[pos] = max(t[pos], x); while((pos /= 2) >= 1) { t[pos] = max(t[pos << 1], t[(pos << 1) ^ 1]); } } int get(int l, int r) { int res = 0; for(l += szT, r += szT; l <= r; l >>= 1, r >>= 1) { if(l & 1) res = max(res, t[l++]); if(!(r & 1)) res = max(res, t[r--]); if(l > r) break; } return res; } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int i = 1; i <= n; ++i) { cin >> a[i]; } for(int i = 1; i <= m; ++i) { int l, r, k; cin >> l >> r >> k; que[r].pb(mkp(l, mkp(k, i))); } for(int i = 1; i <= n; ++i) { while(sz(st) && a[i] >= a[st.top()]) { st.pop(); } if(sz(st)) { upd(st.top(), a[i] + a[st.top()]); } // upd(i, a[i]); for(auto it : que[i]) { int l = it.F; int r = i; int k = it.S.F; int id = it.S.S; if(get(l, r) <= k) { ans[id] = 1; } else { ans[id] = 0; } } st.push(i); } for(int i = 1; i <= m; ++i) { cout << ans[i] <<'\n'; } return 0; } /* If you only do what you can do, You will never be more than you are now! ----------------------------------------- We must all suffer from one of two pains: the pain of discipline or the pain of regret. The difference is discipline weighs grams while regret weighs tons. */
#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...