fork download 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. void Code_By_Mohamed_Khaled() {
  5.     ios_base::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     cout.tie(nullptr);
  8. #ifndef ONLINE_JUDGE
  9.     freopen("input.txt", "r", stdin);
  10.     freopen("output.txt", "w", stdout);
  11. #endif
  12. }
  13. ll n,m;
  14. ll sol(ll p) {
  15.     ll l=1,r=n;
  16.     while (l<r) {
  17.         ll mid=l+(r-l)/2;
  18.         if (mid*(mid+1)/2>=p)r=mid;
  19.         else l=mid+1;
  20.     }
  21.     return l;
  22. }
  23. int main() {
  24.     Code_By_Mohamed_Khaled();
  25.     // freopen("box.in", "r", stdin);
  26.     ll t;cin>>t;
  27.     while(t--) {
  28.         cin>>n>>m;
  29.         ll l=n*(n+1)/2;
  30.         ll ans=n*(n-1)/2;
  31.         map<ll,ll>mp;
  32.         auto get= [&](ll p)->ll {
  33.             auto it=mp.find(p);
  34.             if (it !=mp.end()) return it->second;
  35.             return sol(p);
  36.         };
  37.         auto set= [&](ll p, ll v){
  38.             mp[p]=v;
  39.         };
  40.         for (ll i=1;i<=m;i++) {
  41.             ll x,y;cin>>x>>y;
  42.             if (x==y)continue;
  43.             array<ll,4>v={x-1, x, y-1, y};
  44.             ll before = 0, after = 0;
  45.             for (ll p:v) {
  46.                 if (p>=1 and p+1<=l and get(p)==get(p+1)) before++;
  47.             }
  48.             ll vx=get(x),vy=get(y);
  49.             set(x,vy);
  50.             set(y,vx);
  51.             for (ll p:v) {
  52.                 if (p>=1 and p+1<=l and get(p)==get(p+1))after++;
  53.             }
  54.             ans+=(after-before);
  55.         }
  56.         cout<<ans<<"\n";
  57.     }
  58.     return 0;
  59. }
Success #stdin #stdout 0.01s 5324KB
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 
3
5
https://ideone.com/qRQka2
language:
C++ (gcc 8.3)
created:
9 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!