fork download
copy 
  1. // HeHe vro (^ _ ^)
  2. #ifndef _GLIBCXX_NO_ASSERT
  3. #include <cassert>
  4. #endif
  5. #include <cctype>
  6. #include <cerrno>
  7. #include <cfloat>
  8. #include <ciso646>
  9. #include <climits>
  10. #include <clocale>
  11. #include <cmath>
  12. #include <csetjmp>
  13. #include <csignal>
  14. #include <cstdarg>
  15. #include <cstddef>
  16. #include <cstdio>
  17. #include <cstdlib>
  18. #include <cstring>
  19. #include <ctime>
  20. //
  21. #if __cplusplus >= 201103L
  22. #include <ccomplex>
  23. #include <cfenv>
  24. #include <cinttypes>
  25. //#include <cstdalign>
  26. #include <cstdbool>
  27. #include <cstdint>
  28. #include <ctgmath>
  29. #include <cwchar>
  30. #include <cwctype>
  31. #endif
  32. //
  33. // C++
  34. #include <algorithm>
  35. #include <bitset>
  36. #include <complex>
  37. #include <deque>
  38. #include <exception>
  39. #include <fstream>
  40. #include <functional>
  41. #include <iomanip>
  42. #include <ios>
  43. #include <iosfwd>
  44. #include <iostream>
  45. #include <istream>
  46. #include <iterator>
  47. #include <limits>
  48. #include <list>
  49. #include <locale>
  50. #include <map>
  51. #include <memory>
  52. #include <new>
  53. #include <numeric>
  54. #include <ostream>
  55. #include <queue>
  56. #include <set>
  57. #include <sstream>
  58. #include <stack>
  59. #include <stdexcept>
  60. #include <streambuf>
  61. #include <string>
  62. #include <typeinfo>
  63. #include <utility>
  64. #include <valarray>
  65. #include <vector>
  66. //
  67. #if __cplusplus >= 201103L
  68. #include <array>
  69. #include <atomic>
  70. #include <chrono>
  71. #include <condition_variable>
  72. #include <forward_list>
  73. #include <future>
  74. #include <initializer_list>
  75. #include <mutex>
  76. #include <random>
  77. #include <ratio>
  78. #include <regex>
  79. #include <scoped_allocator>
  80. #include <system_error>
  81. #include <thread>
  82. #include <tuple>
  83. #include <typeindex>
  84. #include <type_traits>
  85. #include <unordered_map>
  86. #include <unordered_set>
  87. #endif
  88. //
  89. #define ll long long int
  90. #define yes cout << "YES" << endl;
  91. #define no cout << "NO" << endl;
  92. #define sp " "
  93. #define nl "\n"
  94. #define sortv sort(v.begin(), v.end())
  95. #define vin vector<int> v(n);
  96. #define vln vector<ll> v(n);
  97. #define miin map<int, int> m;
  98. #define mln map<ll, ll> m;
  99. #define sin set<int> s;
  100. #define sln set<ll> s;
  101. #define rangev v.begin(), v.end()
  102. #define ranges s.begin(), s.end()
  103. #define autom for (auto &z : m)
  104. #define autov for (auto &z : v)
  105. #define autos for (auto &z : s)
  106. #define fori for (int i = 0; i < n; i++)
  107. #define forj for (int j = 0; j < n; j++)
  108. #define get cin >>
  109.  
  110. //------------DEBUG--------------------------------------------------------------------------------------------------------
  111. #ifndef ONLINE_JUDGE
  112. #define debug(x) cerr << #x << " " << x << endl;
  113. #else
  114.  
  115. #define debug(x)
  116.  
  117. #endif
  118. //-------------------------------------------------------------------------------------------------------------------------
  119. using namespace std;
  120.  
  121. const string V = "abcdefghijklmnopqrstuvwxyz";
  122.  
  123.  
  124. void iota(void)
  125. { ll c=0; ll s=0;
  126. ll n; cin>>n>>s;
  127. unordered_map<ll,ll>m;
  128. if(s==0) // all are friends to each other
  129. {
  130. for(int i=n;i>0;i--) c+=i;
  131.  
  132. } else{ 
  133.  
  134. for(int i=0;i<s;i++) //here for each individual try to find his nearest enemy
  135. {
  136.     ll x,y; cin>>x>>y;
  137.     if(y<x)
  138.     {
  139.         swap(x,y);
  140.     }
  141. if(m.find(x)!=m.end())
  142. {
  143.     if(m[x]>y) m[x]=y;
  144. }
  145. else
  146.     m[x]=y;
  147. }
  148. /*till here we have found out for each individual their nearest enemy, but if we consider a subarray, because of other people
  149. in the sub array the no of subarrays would be affected, suppose 1,2,3,4,5... 4and5 are enemy ,if we individually find nearest enemy for each one then;
  150. 1--no enemy(consider 6 to be enemy)
  151. 2--no enemy(consider 6 to be enemy)
  152. 3--no enemy(consider 6 to be enemy)
  153. 4--5
  154. 5--we have considered it already...the last element wont affect because there is no one to its right;
  155. now we have to update the nearest enemy for each individual again;
  156. 1---5
  157. 2---5
  158. 3---5
  159. 4---5
  160. 5--wont affect;
  161. for 1 the subarray is[1,2,3,4,] total subarray(size>1) will be (size-1)=3
  162.     simillarly for others we will calculate;
  163. */
  164. int k=n+1;
  165. for(int i=n-1;i>0;i--)
  166. {
  167.     if(m.find(i)!=m.end())
  168.        {if(m[i]<k)
  169. k=m[i];}
  170. m[i]=k;
  171.  
  172. }
  173. c=n;// each individual is also a candidate for answer
  174. autom
  175. {
  176.     int f=z.second-z.first; 
  177.     c+=f-1;
  178. }
  179. }
  180. cout<<c<<nl;
  181.  
  182.  
  183. }
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191. int main()
  192. {
  193.  
  194. //#ifndef ONLINE_JUDGE
  195.     //freopen("input.txt", "r", stdin);
  196.     //freopen("output.txt", "w", stdout);
  197.    // freopen("Error.txt", "w", stderr);
  198. //#endif
  199.  
  200.     int t;
  201.  
  202.     t = 1;
  203.   cin >> t;
  204.  
  205.     while (t--)
  206.     {
  207.  
  208.        iota();
  209.     }
  210. }
  211. //
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/fZzHMQ
language:
C++14 (gcc 8.3)
created:
1 year 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!