fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. // Binary search to find the type of soldier at position pos
  6. int find_type(int pos) {
  7.     int lo = 1, hi = 2e6;
  8.     while (lo < hi) {
  9.         int mid = (lo + hi) / 2;
  10.         int sum = mid * (mid + 1) / 2;
  11.         if (sum < pos)
  12.             lo = mid + 1;
  13.         else
  14.             hi = mid;
  15.     }
  16.     return lo;
  17. }
  18.  
  19. // Get starting index of type k
  20. int start_index(int k) {
  21.     return (k - 1) * k / 2 + 1;
  22. }
  23.  
  24. int get_type(int pos, map<int, int> &modified) {
  25.     if (modified.count(pos)) return modified[pos];
  26.     return find_type(pos);
  27. }
  28.  
  29. int32_t main() {
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.  
  33.     int T;
  34.     cin >> T;
  35.     while (T--) {
  36.         int N, M;
  37.         cin >> N >> M;
  38.  
  39.         set<int> positions_to_check;
  40.         vector<pair<int, int>> swaps(M);
  41.         for (int i = 0; i < M; ++i) {
  42.             int x, y;
  43.             cin >> x >> y;
  44.             swaps[i] = {x, y};
  45.             for (int d = -1; d <= 1; ++d) {
  46.                 if (x + d >= 1) positions_to_check.insert(x + d);
  47.                 if (y + d >= 1) positions_to_check.insert(y + d);
  48.             }
  49.         }
  50.  
  51.         map<int, int> pos_type;
  52.         for (int pos : positions_to_check) {
  53.             pos_type[pos] = find_type(pos);
  54.         }
  55.  
  56.         for (auto [x, y] : swaps) {
  57.             swap(pos_type[x], pos_type[y]);
  58.         }
  59.  
  60.         int power = 0;
  61.         for (int pos : positions_to_check) {
  62.             if (pos_type.count(pos) && pos_type.count(pos + 1)) {
  63.                 if (pos_type[pos] == pos_type[pos + 1]) power++;
  64.             }
  65.         }
  66.  
  67.         cout << power << '\n';
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin 
2
4 2
1 10
3 4
5 7
13 14
13 9
1 2
7 7
9 4
14 7
8 15
stdout 
0
4
https://ideone.com/JHuwyF
language:
C++ (gcc 8.3)
created:
10 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!