Submission #1217741

#TimeUsernameProblemLanguageResultExecution timeMemory
1217741lopkusHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++20
100 / 100
1848 ms208380 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second struct node{ int s, e, m, val; node *l, *r; node(int S, int E){ s = S, e = E, m = (s+e)/2; val=0; if (s!=e){ l = new node(s, m); r = new node(m+1, e); } } void up(int ind, int nv){ if (s==e)val=max(val, nv); else{ if (ind<=m)l->up(ind, nv); else r->up(ind, nv); val = max(l->val, r->val); } } int query(int left, int right){ if (s==left && e==right)return val; if (right<=m)return l->query(left, right); else if (left>m)return r->query(left, right); else return max(l->query(left, m), r->query(m+1, right)); } }*st; int32_t main(){ int n, q, a, b, c; cin>>n>>q; vector<int> vect(n+1, LLONG_MAX/2), ans(q), l(n+1); vector<vector<pair<int, pii> > > queries(n+1); for (int i=1; i<=n; ++i)cin>>vect[i]; for (int i=0; i<q; ++i){ cin>>a>>b>>c; queries[b].pb(mp(a, mp(c, i))); } stack<int> s; s.push(0); for (int i=1; i<=n; ++i){ while (vect[s.top()]<=vect[i])s.pop(); l[i]=s.top(); s.push(i); } st = new node(0, n); for (int i=1; i<=n; ++i){ st->up(l[i], vect[l[i]]+vect[i]); for (auto c:queries[i])ans[c.se.se]=(st->query(c.fi, i)<=c.se.fi); } for (auto a:ans)cout<<a<<"\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...