Salvens

D

Aug 14th, 2023
952
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11.  
  12. #define int long long
  13. using namespace std;
  14.  
  15. const long long INF = 1e9 + 7;
  16. const int MAXN = 15e4 + 10;
  17. const int N = 1e5 + 10;
  18.  
  19. array<int, MAXN> sq, a, add;
  20. const int B = 666;
  21.  
  22. inline void build(int n) {
  23.     a.fill(0);
  24.     sq.fill(0);
  25.     add.fill(0);
  26. }
  27.  
  28. inline void put(int l, int r) {
  29.     while (l <= r) {
  30.         if (l % B == 0 && l + B - 1 <= r) {
  31.             ++sq[l / B];
  32.             ++add[l / B];
  33.             l += B;
  34.         } else {
  35.             ++a[l];
  36.             sq[l / B] = max(sq[l / B], a[l] + add[l / B]);
  37.             ++l;
  38.         }
  39.     }
  40. }
  41.  
  42. inline int get(int l, int r) {
  43.     int ans = 0;
  44.     while (l <= r) {
  45.         if (l % B == 0 && l + B - 1 <= r) {
  46.             ans = max(ans, sq[l / B]);
  47.             l += B;
  48.         } else {
  49.             ans = max(ans, a[l] + add[l / B]);
  50.             ++l;
  51.         }
  52.     }
  53.     return ans;
  54. }
  55.  
  56. signed main() {
  57.     ios_base::sync_with_stdio(false);
  58.     cin.tie(nullptr);
  59.  
  60.     int n, k, m;
  61.     cin >> n >> k >> m;
  62.     build(n - 1);
  63.     while (m--) {
  64.         int l, r;
  65.         cin >> l >> r;
  66.         --r;
  67.         if (get(l, r) < k) {
  68.             cout << "Yes\n";
  69.             put(l, r);
  70.         } else {
  71.             cout << "No\n";
  72.         }
  73.     }
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment