Submission #1076037

#TimeUsernameProblemLanguageResultExecution timeMemory
1076037dostsHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
427 ms156724 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 = 2e7; 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; nn++; bit.assign(n+1,0); } void put(int p,int v) { p = n-p+1; for(int i=p;i<=n;i+=i&-i) bit[i]+=v; } int get(int p) { p = n-p+1; int ans = 0; for (int i=p;i;i-=i&-i) 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(); for (auto Q : rq[i]){ ans[Q.id] = (ft.get(Q.l) <= Q.k); } ft.put(st.back(),a[i]+a[st.back()]); st.push_back(i); } for (int i=1;i<=q;i++) cout << ans[i] << '\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...