Submission #1010924

#TimeUsernameProblemLanguageResultExecution timeMemory
1010924LucaIlieHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
1351 ms111952 KiB
#include <bits/stdc++.h> using namespace std; struct update { int l, r, k; }; struct query { int l, r, k, ans; }; const int MAX_N = 1e6; const int MAX_Q = 1e6; const int INF = 1e9 + 1; int v[MAX_N + 1]; update updates[MAX_N + 1]; query queries[MAX_Q]; vector<int> queriesByR[MAX_N + 1]; struct AIB_SUF { int aib[MAX_N + 2]; void update( int i, int x ) { i = MAX_N + 1 - i; while ( i <= MAX_N ) { aib[i] = max( aib[i], x ); i += (i & -i); } } int query( int i ) { i = MAX_N + 1 - i; int x = 0; while ( i > 0 ) { x = max( x, aib[i] ); i -= (i & -i); } return x; } } maxKSuf; int main() { int n, q; cin >> n >> q; v[0] = INF; for ( int i = 1; i <= n; i++ ) cin >> v[i]; for ( int i = 0; i < q; i++ ) cin >> queries[i].l >> queries[i].r >> queries[i].k; vector<int> stack; stack.push_back( 0 ); for ( int i = 1; i <= n; i++ ) { while ( !stack.empty() && v[i] >= v[stack.back()] ) stack.pop_back(); updates[i] = { stack.back(), i, v[stack.back()] + v[i] }; stack.push_back( i ); } for ( int i = 0; i < q; i++ ) queriesByR[queries[i].r].push_back( i ); for ( int i = 1; i <= n; i++ ) { maxKSuf.update( updates[i].l, updates[i].k ); for ( int j: queriesByR[i] ) queries[j].ans = maxKSuf.query( queries[j].l ); } for ( int i = 0; i < q; i++ ) cout << (queries[i].ans <= queries[i].k) << "\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...