fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define vi vector<int>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ii pair<int , int>
  9. #define pq priority_queue
  10. #define iii pair<int , pair<int , int>>
  11. #define fo(i,l,r) for(int i=l;i<=r;i++)
  12. #define fod(i,r,l) for(int i=r;i>=l;i--)
  13. #define fill(f,x) memset(f,x,sizeof(f))
  14. #define NAME "file"
  15.  
  16. const int N = 3e5 + 5, mod = 1e9 + 7;
  17. int n, m, A[N], bit[N], u[N], v[N], x[N], a[N], l[N], r[N], y[N];
  18. vector <int> q[N];
  19.  
  20. struct add
  21. {
  22. int i, x, u, v;
  23. } st[N];
  24.  
  25.  
  26. void upd(int x , int v)
  27. {
  28. for (; x <= 1e5; x += x & -x) bit[x] += v;
  29. }
  30.  
  31. int get(int x)
  32. {
  33. int res = 0;
  34. for (; x > 0 ; x &= x - 1) res += bit[x];
  35. return res;
  36. }
  37.  
  38. bool cmp(add a , add b)
  39. {
  40. return a.x < b.x;
  41. }
  42.  
  43.  
  44. signed main()
  45. {
  46. ios_base::sync_with_stdio(0);
  47. cin.tie(0); cout.tie(0);
  48. //freopen(NAME".INP" , "r" , stdin);
  49. //freopen(NAME".OUT" , "w" , stdout);
  50.  
  51. cin >> n >> m;
  52. fo(i, 1, n)
  53. cin >> A[i];
  54.  
  55. fo(i, 1, m)
  56. {
  57. cin >> u[i] >> v[i] >> x[i] >> a[i];
  58. st[i].i = i;
  59. st[i].u = u[i];
  60. st[i].v = v[i];
  61. st[i].x = x[i];
  62. }
  63.  
  64. sort(st + 1 , st + m + 1 , cmp);
  65. int j = 0;
  66. fo(i, 1, m)
  67. {
  68. while (j + 1 < st[i].x)
  69. {
  70. j++;
  71. upd(A[j] , 1);
  72. }
  73. int k = get(st[i].v) - get(st[i].u - 1);
  74. a[st[i].i] += k;
  75. }
  76.  
  77. fo(i, 1, 1e5) bit[i] = 0;
  78.  
  79. //
  80.  
  81. fo(i, 1, m)
  82. {
  83. l[i] = 1;
  84. r[i] = n;
  85. y[i] = -1;
  86. }
  87.  
  88. bool run = 1;
  89. while (run)
  90. {
  91. run = 0;
  92.  
  93. fo(i, 1, m)
  94. {
  95. if (l[i] <= r[i])
  96. {
  97. run = 1;
  98. q[(l[i] + r[i]) / 2].push_back(i);
  99. }
  100. }
  101.  
  102. fo(mid, 1, n)
  103. {
  104. upd(A[mid] , 1);
  105.  
  106. for (auto i : q[mid])
  107. {
  108. int sum = get(v[i]) - get(u[i] - 1);
  109. if (sum >= a[i])
  110. {
  111. y[i] = mid;
  112. r[i] = mid - 1;
  113. }
  114. else
  115. l[i] = mid + 1;
  116. }
  117. }
  118.  
  119. fo(i, 1, m) q[i].clear();
  120. fo(i, 1, 1e5) bit[i] = 0;
  121. }
  122.  
  123. fo(i, 1, m)
  124. cout << y[i] << ' ';
  125. }
  126. // haronnee_
Success #stdin #stdout 0.01s 12892KB
stdin
Standard input is empty
stdout
Standard output is empty