Submission #1171708

#TimeUsernameProblemLanguageResultExecution timeMemory
1171708LilPlutonHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
824 ms105268 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define ar array #define vc vector #define all(x) x.begin(), x.end() #define sortall(x) sort(all(x)) #define rep(i,a,b) for(int i = a; i < b; i++) #define per(i,a,b) for(int i = a; i >= b; i--) #define trav(a,x) for(auto& a : x) #define sz(x) (int)(x).size() #define ff first #define ss second #define pb push_back #define mp make_pair #define endl '\n' #define debug(x) cerr << #x << " = " << x << endl const int N = 1e6 + 5; const int inf = 1e15; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> vector<int> st(N * 4), a(N); void upd(int node,int tl,int tr,int l,int r,int val){ if(r < tl || l > tr){ return; } if(l <= tl && tr <= r){ st[node] = max(st[node], val); return; } int mid = (tl + tr) >> 1; upd(node * 2, tl, mid, l, r, val); upd(node * 2 + 1, mid + 1, tr, l, r, val); st[node] = max(st[node * 2], st[node * 2 + 1]); } int get(int node,int tl,int tr,int l,int r){ if(r < tl || l > tr){ return 0; } if(l <= tl && tr <= r){ return st[node]; } int mid = (tl + tr) >> 1; return max(get(node * 2, tl, mid, l, r), get(node * 2 + 1, mid + 1, tr, l, r)); } void solve(){ int n, q; cin >> n >> q; for(int i = 1; i <= n; ++i){ cin >> a[i]; } stack<int> stck; vector<vector<ar<int,3>>> qr(n + 1); for(int i = 0; i < q; ++i){ int l, r, k; cin >> l >> r >> k; qr[r].pb({l, k, i}); } vector<int> res(q); for(int i = 1; i <= n; ++i){ while(!stck.empty() && a[stck.top()] < a[i]){ stck.pop(); } if(!stck.empty()){ upd(1, 1, n, stck.top(), n, a[stck.top()] + a[i]); } stck.push(i); for(auto j : qr[i]){ res[j[2]] = (get(1, 1, n, j[0], n) <= j[1]); } } for(auto i : res){ cout << i << endl; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); int T = 1; while(T--){ solve(); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...