Submission #497903

#TimeUsernameProblemLanguageResultExecution timeMemory
497903IerusHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
2885 ms91332 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; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define S second #define sz(x) (int)x.size() #define int long long #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) //#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> typedef long long ll; const int E = 1e6+777; const long long inf = 1e18+777; const int N = 1e5+777; const int MOD = 1e9+7; const bool I = 1; int n, que, a[E], t[E<<2], ans[E]; void update(int pos, int val, int v, int tl, int tr){ if(tl == tr){ t[v] = max(val, t[v]); return; } int tm = (tl + tr) / 2; if(pos <= tm) update(pos, val, v<<1, tl, tm); else update(pos, val, v<<1|1, tm+1, tr); t[v] = max(t[v<<1], t[v<<1|1]); } int get(int l, int r, int v, int tl, int tr){ if(l <= tl && tr <= r) return t[v]; if(tl > r || tr < l) return 0; int tm = (tl + tr) / 2; return max(get(l, r, v<<1, tl, tm), get(l, r, v<<1|1, tm+1, tr)); } struct D{ int l, x, i; }; vector<D> g[E]; signed main(){ cin >> n >> que; for(int i = 1; i <= n; ++i){ cin >> a[i]; } for(int l, r, x, i = 1; i <= que; ++i){ cin >> l >> r >> x; g[r].pb({l, x, i}); } deque<pair<int,int>> st; for(int i = 1; i <= n; ++i){ while(!st.empty() && st.back().F <= a[i]) st.pop_back(); if(!st.empty()) update(st.back().S, st.back().F + a[i], 1, 0, n); for(auto to : g[i]){ int cur = get(to.l, i, 1, 0, n); ans[to.i] = (cur <= to.x); } st.push_back({a[i], i}); } for(int i = 1; i <= que; ++i){ cout << ans[i] << '\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...