Submission #151538

#TimeUsernameProblemLanguageResultExecution timeMemory
151538andrewHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
64 / 100
3023 ms29804 KiB
#include <bits/stdc++.h> #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define p_b push_back #define pll pair<ll,ll> #define pii pair<int,int> #define m_p make_pair #define all(x) x.begin(),x.end() #define sqr(x) (x)*(x) #define pw(x) (1ll << x) using namespace std; typedef int ll; typedef long double ld; const ll MAXN = 1123456; const ll N = 1e6 + 5; mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count()); template <typename T> void vout(T s){cout << s << endl;exit(0);} vector<pair<ll, ll> > v; pair<pair<ll, ll>, ll> b[N]; vector<ll> q; ll t[4 * N],a[N],n,Q,limit,l,r,x,k,ans[N]; void upd(ll v,ll tl,ll tr,ll pos,ll val) { if(tl == tr) { t[v] = val + a[tl]; return; } ll tm = (tl + tr) / 2; if(pos <= tm) upd(2 * v, tl, tm, pos, val); else upd(2 * v + 1, tm + 1, tr, pos, val); t[v] = max(t[2 * v], t[2 * v + 1]); } ll get(ll v,ll tl,ll tr,ll l,ll r) { if(l > r) return 0; if(tl == l && tr == r) return t[v]; ll tm = (tl + tr) / 2; return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)); } void make(ll l,ll r) { for(int i = r; i >= l; i--) { ll x = a[i],pos; while(!v.empty() && x > v.back().fi) { pos = v.back().se; upd(1, 1, n, pos, x); v.pop_back(); } v.push_back({x, i}); } } bool comp(ll i,ll j) { return b[i].fi.fi > b[j].fi.fi; } int main() { ios_base::sync_with_stdio();cin.tie(0);cout.tie(0); cin>>n>>Q; for(int i = 1; i <= n; i++) cin>>a[i]; limit = n; for(int i = 1; i <= Q; i++) { cin>>l>>r>>x; b[i] = {{l, r}, x}; q.push_back(i); } sort(all(q), comp); for(auto i : q) { l = b[i].fi.fi; r = b[i].fi.se; k = b[i].se; if(limit >= l) { make(l, limit); limit = l - 1; } x = get(1, 1, n, l, r); ans[i] = (x <= k); } for(int i = 1; i <= Q; i++) cout<<ans[i]<<"\n"; 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...