fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb push_back
  17.  
  18. #define totalone(mask) __builtin_popcount(mask)
  19. #define chkbit(mask,bit) (mask&(1LL << bit))
  20. #define setbit(mask,bit) (mask|(1LL << bit))
  21. #define cngbit(mask,bit) (mask^(1LL << bit))
  22.  
  23. #define en "\n"
  24. #define dbg(x) cerr<<#x<<" is : "<<x<<en;
  25. #define yes cout<<"YES\n"
  26. #define no cout<<"NO\n"
  27. #define report cout<<-1<<en
  28. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  29. #define sqr(n) (1LL*(n)*(n))
  30. #define vag(a,b) ((a + b - 1)/b)
  31. #define coutv(v) for(auto i: v) cout<<i<<" ";cout<<en;
  32. #define cinv(v) for(auto &i: v) cin >> i;
  33.  
  34. #define MAXN 50010
  35. #define inf 1e6+5
  36. const int mod = 1e9 + 7;
  37.  
  38. vector<int>mn, mx;
  39. struct segment_tree
  40. {
  41.     struct node {
  42.         int suru , ses;
  43.         vector<int>v;
  44.  
  45.         void init(int l, int r) {
  46.             v.clear();
  47.             suru = l, ses = r;
  48.             for (int i = l; i <= r; i++) v.pb(mn[i]);
  49.             sort(all(v));
  50.         }
  51.     } g[4 * MAXN];
  52.  
  53.  
  54.     void build(int cn, int l, int r)
  55.     {
  56.         g[cn].init(l, r);
  57.  
  58.         if (l == r ) return;
  59.         int md = l + (r - l) / 2;
  60.  
  61.         build(cn * 2, l, md);
  62.         build(cn * 2 + 1, md + 1, r);
  63.     }
  64.  
  65.     int query(int cn, int l, int r, int val)
  66.     {
  67.         int x = g[cn].suru;
  68.         int y = g[cn].ses;
  69.         if (y < l || x > r) return 0;
  70.  
  71.         if (l <= x && r >= y ) {
  72.             // coutv(g[cn].v);
  73.             int lb = upper_bound(all(g[cn].v), val) - g[cn].v.begin();
  74.             return  lb;
  75.         }
  76.  
  77.         int ans = query(cn * 2, l, r, val);
  78.         ans +=  query(cn * 2 + 1, l, r, val);
  79.         return ans;
  80.     }
  81.  
  82. } stre;
  83.  
  84.  
  85. void solve()
  86. {
  87.     int n, q;
  88.     cin >> n >> q;
  89.  
  90.     vector<pair<int, int>>v;
  91.  
  92.     mn.clear();
  93.     mx.clear();
  94.  
  95.     for (int i = 0; i < n; i++) {
  96.         int x, y;
  97.         cin >> x >> y;
  98.         v.pb({y, x});
  99.         mx.pb(y);
  100.     }
  101.  
  102.     sort(all(mx));
  103.     sort(all(v));
  104.  
  105.     for (int i = 0; i < n; i++) {
  106.         mn.pb(v[i].sn);
  107.     }
  108.  
  109.     stre.build(1, 0, n - 1);
  110.  
  111.     while (q--)
  112.     {
  113.         int x;
  114.         cin >> x;
  115.  
  116.         int lb = lower_bound(all(mx), x) - mx.begin();
  117.         if (lb == n) cout << 0 << en;
  118.         else
  119.             cout << stre.query(1, lb, n - 1, x) << en;
  120.  
  121.     }
  122.  
  123.  
  124. }
  125. int main()
  126. {
  127.     IOS;
  128.     ll t;
  129.     t = 1;
  130.     cin >> t;
  131.  
  132.     int c = 0;
  133.     while ( t-- )
  134.     {
  135.         cout << "Case " << ++c << ":\n";
  136.         solve();
  137.     }
  138.     return 0;
  139. }
Runtime error #stdin #stdout 0.01s 9660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X82yCw
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!