fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4.  
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7.  
  8. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  9.  
  10. #define endl     '\n'
  11. #define int      long long
  12.  
  13. const int N = 2e5, oo = 2e18, MOD = 998244353;
  14.  
  15.  
  16. // 1 3 -> 3
  17. // 3 4 -> 2
  18. // 4 7 -> 2
  19. // 5 8 -> 2
  20.  
  21. class SegTree {
  22. private:
  23.     struct Node {
  24.         int content;
  25.  
  26.         Node() { content = 0; }
  27.         Node(int data) { content = data; }
  28.         void update(int data) { content += data; }
  29.     };
  30.  
  31.     int size;
  32.     vector<Node> tree;
  33.     void build(vector<int> &arr, int n, int ni, int lx, int rx) {
  34.         if (rx - lx == 1) {
  35.             if (lx < n)
  36.                 tree[ni] = Node(arr[lx]);
  37.             return;
  38.         }
  39.         int mid = (lx + rx) / 2;
  40.         build(arr, n, 2 * ni + 1, lx, mid);
  41.         build(arr, n, 2 * ni + 2, mid, rx);
  42.         tree[ni] = merge(tree[2 * ni + 1], tree[2 * ni + 2]);
  43.     }
  44.     Node merge(Node a, Node b) { return Node(a.content + b.content); }
  45.     void update(int idx, int val, int ni, int lx, int rx) {
  46.         if (rx - lx == 1) {
  47.             tree[ni].update(val);
  48.             return;
  49.         }
  50.         int mid = (lx + rx) / 2;
  51.         if (idx < mid) {
  52.             update(idx, val, 2 * ni + 1, lx, mid);
  53.         } else {
  54.             update(idx, val, 2 * ni + 2, mid, rx);
  55.         }
  56.         tree[ni] = merge(tree[2 * ni + 1], tree[2 * ni + 2]);
  57.     }
  58.      Node get(int l, int r, int ni, int lx, int rx) {
  59.         if (rx <= l || lx >= r) {
  60.             return Node();
  61.         }
  62.         if (lx >= l && rx <= r) {
  63.             return tree[ni];
  64.         }
  65.         int mid = (lx + rx) / 2;
  66.         return merge(get(l, r, 2 * ni + 1, lx, mid), get(l, r, 2 * ni + 2, mid, rx));
  67.     }
  68.  
  69. public:
  70.     SegTree(vector<int> &arr) {
  71.         int n = arr.size();
  72.         size = 1;
  73.         while (size < n) {
  74.             size *= 2;
  75.         }
  76.         tree.assign(2 * size, Node());
  77.         build(arr, n, 0, 0, size);
  78.     }
  79.     void update(int idx, int val) { update(idx, val, 0, 0, size); }
  80.     int get(int l, int r) { return get(l, r + 1, 0, 0, size).content; }
  81. };
  82.  
  83. struct coordinate_compression {
  84. private:
  85.     vector<long long> comp; // A vector to store the unique, sorted elements for compression.
  86.  
  87.     // A private method to perform compression by sorting and removing duplicates.
  88.     void compress() {
  89.         sort(comp.begin(), comp.end()); // Sort the vector to arrange elements in ascending order.
  90.         comp.erase(unique(comp.begin(), comp.end()), comp.end()); // Remove duplicates to keep only unique elements.
  91.     }
  92.  
  93. public:
  94.     // Constructor that initializes the compression vector with the input and compresses it.
  95.     coordinate_compression(vector<long long> & v) {
  96.         comp = v; // Copy the input vector to the internal 'comp' vector.
  97.         compress(); // Call the compress function to sort and remove duplicates.
  98.     }
  99.     int cnt() {
  100.         return comp.size();
  101.     }
  102.     // Method to get the compressed index of a given value.
  103.     int get_index(long long val) {
  104.         return lower_bound(comp.begin(), comp.end(), val) - comp.begin(); 
  105.         // Finds the position where 'val' fits in the sorted 'comp' vector.
  106.         // Subtracting comp.begin() gives the zero-based index of 'val'.
  107.         // If a 1-based index is needed, add +1 to the result.
  108.     }
  109.  
  110.     // Method to get the original value from the compressed index.
  111.     int get_origin(size_t idx) {
  112.         return comp[idx]; // Returns the original value corresponding to the given index in the compressed vector.
  113.     }
  114. };
  115.  
  116.  
  117.  
  118. void solve() {
  119.     int n, k; cin >> n >> k;
  120.     vector<pair<int, int>> a(n);
  121.     vector<int> c;
  122.     for (int i = 0; i < n ; i++) {
  123.         cin >> a[i].first >> a[i].second;
  124.         c.push_back(a[i].first);
  125.         c.push_back(a[i].second);
  126.     }
  127.     sort(a.begin(), a.end());
  128.     coordinate_compression comp(c);
  129.     for (int i = 0; i < n ; i++) {
  130.         a[i].first = comp.get_index(a[i].first);
  131.         a[i].second = comp.get_index(a[i].second);
  132.     }
  133.     int cnt = comp.cnt();
  134.     vector<int> b(cnt);
  135.     SegTree tree(b);
  136.     int ans = 1;
  137.     for (int i = 0; i < n; i++) {
  138.         int c = tree.get(a[i].first, cnt - 1);
  139.         if (c >= k) {
  140.             cout << 0 << endl;
  141.             return;
  142.         }
  143.         ans = (ans * (k - c)) % MOD;
  144.         tree.update(a[i].second, 1);
  145.     }
  146.     cout << ans << endl;
  147. }
  148.  
  149.  
  150. signed main() {
  151.     ios_base::sync_with_stdio(false); 
  152.     cin.tie(NULL); cout.tie(NULL);
  153.     // #ifndef ONLINE_JUDGE 
  154.     //    freopen("input.txt", "r", stdin); 
  155.     //    freopen("output.txt", "w", stdout); 
  156.     // #endif 
  157.     int t; t = 1;
  158.     cin >> t;
  159.     while (t--) solve();
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
28804401
https://ideone.com/u38VCU
language:
C++ (gcc 8.3)
created:
11 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!