Submission #1076053

#TimeUsernameProblemLanguageResultExecution timeMemory
1076053dostsHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
640 ms158812 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> const int MOD = 1e9+7,inf = 2e18; const int N = 5001; struct Query { int l=0,r=0,k=0,id=0; }; struct FT { int n; vi bit; FT(int nn) { n = nn; bit.assign(n+1,0); } void put(int p,int v) { for(int i=p;i<=n;i+=i&-i) bit[i]=max(bit[i],v); } int get(int p) { int ans = 0; for (int i=p;i>0;i-=i&-i) ans=max(ans,bit[i]); return ans; } }; void solve() { int n,q; cin >> n >> q; vi a(n+1); for (int i=1;i<=n;i++) cin >> a[i]; vector<Query> queries(q+1); for (int i=1;i<=q;i++) { Query& Q = queries[i]; cin >> Q.l >> Q.r >> Q.k; Q.id = i; } vector<Query> rq[n+1]; for (int i=1;i<=q;i++) { rq[queries[i].r].push_back(queries[i]); } vi ans(q+1); a[0] = inf; FT ft(n); vi st{0}; for (int i=1;i<=n;i++) { while (a[st.back()] <= a[i]) st.pop_back(); if (st.back()) ft.put(n-st.back()+1,a[i]+a[st.back()]); for (auto Q : rq[i]){ ans[Q.id] = ft.get(n-Q.l+1); } st.push_back(i); } for (int i=1;i<=q;i++) cout << (ans[i]<=queries[i].k) << '\n'; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#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...