Submission #1112794

#TimeUsernameProblemLanguageResultExecution timeMemory
1112794vjudge1Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
1160 ms128120 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; #define ll long long #define int long long #define ar array //#define endl '\n' const int N = 1e6 + 20; const int MOD = 1e9 + 7; const int INF = 1e9; const int LOG = 30; struct seggy{ struct Node{ int mn, mx, ans; Node(int x = 0){ ans = 0; mn = min(0ll, x); mx = max(0ll, x); } Node(int a,int b,int c){ mn = a, mx = b, ans = c; } }; Node merge(Node a, Node b){ Node res; res.mx = max(a.mx, b.mx); res.mn = min(a.mn, b.mn); res.ans = max({a.ans, b.ans, a.mx - b.mx}); return res; } vector<Node> s; void init(int n){ s.resize(4 * n + 69); } void upd(int k,int tl,int tr,int p,int v){ if(tl == tr){ s[k] = Node(v); return; } int tm = (tl + tr) / 2; if(p <= tm)upd(k * 2, tl, tm, p, v); else upd(k * 2 + 1, tm + 1, tr, p, v); s[k] = merge(s[k * 2], s[k * 2 + 1]); } Node qry(int k,int tl,int tr,int l,int r){ if(l > tr || tl > r)return Node(); if(l <= tl && tr <= r)return s[k]; int tm = (tl + tr) / 2; return merge(qry(k * 2,tl, tm, l, r), qry(k * 2 + 1,tm + 1, tr, l, r)); } }; signed main(){ios::sync_with_stdio(false);cin.tie(0); int n, q; cin>>n>>q; seggy sgt; sgt.init(n); for(int i = 0;i < n;i++){ int x; cin>>x; sgt.upd(1, 0, n - 1,i, x); } while(q--){ int l, r, k; cin>>l>>r>>k; --l, --r; //cout<<sgt.qry(1, 0, n- 1,l, r).ans<<'\n'; if(sgt.qry(1, 0, n- 1,l, r).ans <= k)cout<<"1\n"; else cout<<"0\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...