fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. typedef pair<int, int> pp;
  7.  
  8. template<typename T1, typename T2>
  9. ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  10.     return os << p.first << " " << p.second;
  11. }
  12.  
  13. #define all(a) (a).begin(), (a).end()
  14. #define what_is(x) cerr << #x << " is " << x << '\n';
  15. #define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';
  16.  
  17. const int N = 2e5 + 7;
  18. const int MOD = 1e9 + 7;
  19. const int INF = 1e15;
  20. const int M = 1e6 + 2;
  21.  
  22. int pre[M] {};
  23. vector<int> levels[N], K[N];
  24. int ans[10003];
  25. vector<pp> X[2002];
  26. int suf[N] {};
  27. bool mrk[M] {};
  28.  
  29. void solve() {
  30.     // Don't forget
  31.     //
  32.     // 1. If you are looking at editorial, remember that you are accepting defeat.
  33.     // the problem defeated you
  34.     // 2. [If stuck] Don't stick to one approach and attack with different approaches.
  35.     // Write everything down, analyse the G-spot and attack through it.
  36.  
  37.     // 3. Fix l, r, or i, and if necessary give it a value.
  38.  
  39.     int n, m;
  40.     cin >> n >> m;
  41.  
  42.  
  43.     for (int i = 0, l, r; i < n; ++i) {
  44.         cin >> l >> r;
  45.         pre[l]++;
  46.         pre[r + 1] --;
  47.     }
  48.  
  49.  
  50.  
  51.     for (int i = 1; i <= m; ++i) {
  52.         pre[i] += pre[i - 1];
  53.     }
  54.  
  55.     // 1- Identify each level
  56.  
  57.     vector<int> douts(m);
  58.     iota(all(douts), 1ll);
  59.  
  60.     // for (auto &x : douts) {
  61.     //     cout << x << ' ';
  62.     // }
  63.     // cout << endl;
  64.  
  65.     for (int i = 20; i > 10; --i) {
  66.         vector<int> have;
  67.         for (auto &x : douts) {
  68.             if ((1<<i) & x) have.emplace_back(x);
  69.         }
  70.         if (have.size()) douts = have;
  71.     }
  72.  
  73.     vector<pp> l_v;
  74.  
  75.     for (auto x : douts) {
  76.         mrk[x] = true;
  77.         l_v.emplace_back(pre[x], x);
  78.     }
  79.  
  80.     sort(l_v.rbegin(), l_v.rend());
  81.  
  82.     for (int i = 1; i <= m; ++i) {
  83.         if (mrk[i]) continue;
  84.         levels[pre[i]].push_back(i);
  85.     }
  86.  
  87.     for (int i = n; i >= 1; --i) {
  88.         suf[i] = suf[i + 1] + levels[i].size();
  89.     }
  90.  
  91.     // 2- reading the queries and sort them based on k
  92.     int q; cin >> q;
  93.  
  94.     for (int i = 0, x, k; i < q; ++i) {
  95.         cin >> x >> k;
  96.         X[x].emplace_back(k, i);
  97.     }
  98.  
  99.     // 3- Loop for each x and determine it independenlty
  100.     int limit = min(2000ll, m);
  101.  
  102.     for (int x = 1; x <= limit; ++x) {
  103.         if (!X[x].size()) continue;
  104.  
  105.  
  106.         int sum = 0;
  107.         int xl = pre[x];
  108.  
  109.         map<int, int> mp;
  110.  
  111.         for (auto [level, num] : l_v) {
  112.             int y = num ^ x;
  113.             if (1 <= y && y <= m) {
  114.                 if (mp.count(level)) mp[level]++;
  115.                 else {
  116.                     auto it = mp.upper_bound(level);
  117.                     if (it != mp.end()) mp[level] = it->second;
  118.                     mp[level]++;
  119.                 }
  120.             }
  121.         }
  122.  
  123.         for (auto [k, i] : X[x]) {
  124.             auto it = mp.lower_bound(k);
  125.             int s1 = (it != mp.end() ? it->second : 0);
  126.             int s2 = suf[k];
  127.  
  128.             if (!mrk[x] && pre[x] >= k) s2--;
  129.  
  130.             ans[i] = s1 + s2;
  131.         }
  132.     }
  133.  
  134.  
  135.  
  136.     for (int i = 0; i < q; ++i) {
  137.         cout << ans[i] << '\n';
  138.     }
  139.  
  140.  
  141.  
  142.             // 3. Don't look at standings during the contest.
  143.  
  144.             // 4. Don't try to code fast and code concetrately instead or bugs will annoy you
  145.  
  146. }
  147.  
  148. int32_t main() {
  149.     ios_base::sync_with_stdio(false);
  150.     cin.tie(nullptr);
  151.     cout.tie(nullptr);
  152.  
  153. #ifndef ONLINE_JUDGE
  154.     freopen("input.txt", "r", stdin);
  155.     freopen("output.txt", "w", stdout);
  156. #endif
  157.  
  158.     int tt = 1;
  159.     // cin >> tt;
  160.     while (tt--) {
  161.         solve();
  162.     }
  163.  
  164.     return 0;
  165. }
Success #stdin #stdout 0.01s 15888KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Y7QbW2
language:
C++ (gcc 8.3)
created:
4 days 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!