Submission #1172135

#TimeUsernameProblemLanguageResultExecution timeMemory
1172135Hurryup_7735Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++20
0 / 100
37 ms7436 KiB
//In The Name Of ALLAH! #pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define ld long double #define endl '\n' #define pb push_back #define pf push_front #define speedyboy ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define bpc __builtin_popcount #define all(x) x.begin() , x.end() #define allr(x) x.rbegin() , x.rend() #define F first #define S second #define pll pair<ll , ll> #define turtle tuple<ll , ll , ll , ll> #define pss pair<string , string> #define YES cout << "YES" << endl; #define NO cout << "NO" << endl; #define ordered_set tree<ll , null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update> const ll sz = 2e5 + 5 , INF = 1e18 , MOD = 998244353; ll a[sz] , st[sz<<2] , res[sz]; void update(ll l , ll r , ll in , ll x , ll val){ if(x < l || r < x) return; if(l == r){ st[in] = val; return; } ll mid = (l + r)>>1; update(l , mid , in<<1 , x , val); update(mid + 1 , r , in<<1|1 , x , val); st[in] = max(st[in<<1] , st[in<<1|1]); } ll getans(ll a , ll b , ll l , ll r , ll in){ if(a > r || l > b) return -INF; if(a <= l && r <= b) return st[in]; ll mid = (l + r)>>1; return max(getans(a , b , l , mid , in<<1) , getans(a , b , mid + 1 , r , in<<1|1)); } ll mask , i , j , o; void solve(){ ll n , q; cin >> n >> q; for(i = 1 ; i <= n ; i++) cin >> a[i]; vector<array<ll , 4>> v(q + 1); for(i = 1 ; i <= q ; i++){ cin >> v[i][0] >> v[i][1] >> v[i][2]; v[i][3] = i; } sort(all(v)); stack<ll> s; ll last = 0; for(i = 0 ; i < q ; i++){ ll r = v[i][0] , l = v[i][1] , k = v[i][2] , ind = v[i][3]; if(last < r){ for(j = last + 1 ; j <= r ; j++){ while(!s.empty() && a[s.top()] <= a[j]) s.pop(); if(!s.empty()){ ll x = s.top(); update(1 , n , 1 , x , a[j] + a[x]); } s.push(j); } last = r; } ll ans = getans(l , r , 1 , n , 1); res[ind] = (ans > k ? 0 : 1); } for(i = 1 ; i <= q ; i++) cout << res[i] << endl; } signed main(){ speedyboy; //open; ll t = 1; //cin >> t; while(t--){ 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...