Submission #1171712

#TimeUsernameProblemLanguageResultExecution timeMemory
1171712LilPlutonHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
625 ms81868 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> int ft[N], a[N]; int n, q; void upd (int x, int v) { for (; x > 0; x -= x & (-x)) { ft[x] = max(ft[x], v); } } int get (int x) { int mx = -inf; for (; x <= n; x += x & (-x)) { mx = max(mx, ft[x]); } return mx; } void solve(){ 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(stck.top(), a[stck.top()] + a[i]); } stck.push(i); for(auto [l, k, id] : qr[i]){ res[id] = (get(l) <= k ? 1 : 0); } } 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...