fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200005;
  5. long long a[N], pref[N];
  6. int n, q;
  7. long long k;
  8.  
  9. // Sparse Table
  10. int st[20][N];
  11. int lg[N];
  12.  
  13. void build() {
  14.     for (int i = 1; i <= n; i++) st[0][i] = a[i];
  15.  
  16.     for (int j = 1; (1 << j) <= n; j++) {
  17.         for (int i = 1; i + (1 << j) - 1 <= n; i++) {
  18.             st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))]);
  19.         }
  20.     }
  21.  
  22.     for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
  23. }
  24.  
  25. int get_max(int l, int r) {
  26.     int j = lg[r - l + 1];
  27.     return max(st[j][l], st[j][r - (1 << j) + 1]);
  28. }
  29.  
  30. int main() {
  31.     ios::sync_with_stdio(false);
  32.     cin.tie(NULL);
  33.  
  34.     cin >> n >> k >> q;
  35.     for (int i = 1; i <= n; i++) {
  36.         cin >> a[i];
  37.         pref[i] = pref[i-1] + a[i];
  38.     }
  39.  
  40.     build();
  41.  
  42.     while (q--) {
  43.         int l, r;
  44.         cin >> l >> r;
  45.  
  46.         long long M = get_max(l, r);
  47.         long long sum = pref[r] - pref[l-1];
  48.         long long len = r - l + 1;
  49.  
  50.         long long cost = len * M - sum;
  51.  
  52.         if (cost <= k) cout << "YES\n";
  53.         else cout << "NO\n";
  54.     }
  55. }
  56.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/CpEMPF
language:
C++ (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!