fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD (ll)998244353
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=3*1e5;
  18. ll ans = 0 ;
  19. ll Than[Max_n+3] ;
  20. struct bacfoi{
  21. 	int a , b ;
  22. } ;
  23. bacfoi a[Max_n+3] ;
  24.  
  25. bool cmp (bacfoi a , bacfoi b){
  26. 	return a.a < b.a ; 
  27. }
  28. bool cmp_for_b (bacfoi a , bacfoi b) {
  29. 	return a.b < b.b ;
  30. }
  31. bool cmp_for_a_but_need_b ( bacfoi a , bacfoi b) {
  32. 	return (a.a!=b.a)?(a.a<b.a):(a.b < b.b) ;
  33. }
  34. void solve(){
  35.  
  36. 	int n ; cin >> n ;
  37. 	Than[0] = 1 ;
  38. 	for (int i = 1 ; i <= n ; i ++ ){
  39. 		Than[i] = (Than[i-1] ) * ( i % MOD );
  40. 		Than[i] %= MOD ; 
  41. 	}
  42. 	for (int i = 1 ; i <= n ; i ++ ){
  43. 		cin >> a[i].a >> a[i].b ;
  44. 	}
  45. 	sort ( a + 1 , a + n + 1 , cmp ) ; 
  46. 	a[0].b = 
  47. 	a[0].a = -1 ;
  48. 	int dem = 1 ;
  49. 	ll ans_1 = 1 ;
  50. 	for (int i = 1 ; i <= n ; i ++ ){
  51. 		if ( a[i].a == a[i+1].a ){
  52. 			dem ++ ;
  53. 		}
  54. 		else {
  55. 			//cerr << ans_1 << ' ' << dem << '\n';
  56. 			ans_1 *= (Than[dem]) ;
  57. 			ans_1 %=MOD ; 
  58. 			dem = 1 ;
  59. 		}
  60. 	}
  61. 	cerr << ans_1 << '\n';
  62. 	sort ( a + 1 , a + n + 1 , cmp_for_b ) ; 
  63. 	dem = 1 ;
  64. 	ll ans_2 = 1 ;
  65. 	for (int i = 1 ; i <= n ; i ++ ){
  66. 		if ( a[i].b == a[i+1].b ){
  67. 			dem ++ ;
  68. 		}
  69. 		else {
  70. 			ans_2 *= (Than[dem]) ;
  71. 			ans_2 %=MOD ; 
  72. 			dem = 1 ;
  73. 		}
  74. 	}
  75. 	sort ( a + 1 , a + n + 1 , cmp_for_a_but_need_b ) ; 
  76. 	bool check_run = 1 ; 
  77. 	for (int i = 2 ; i <= n ; i ++ ){
  78. 		if (a[i].b < a[i-1].b) {
  79. 			check_run = 0 ;
  80. 			break ;
  81. 		}
  82. 	}
  83. 	ll ans_3 = 1 ;
  84. 	if ( check_run ) {
  85. 		dem = 1 ;
  86. 		for (int i = 2 ; i <= n ; i ++ ){
  87. 			if ( a[i].a == a[i-1].a && a[i].b == a[i-1].b){
  88. 				dem++ ;
  89. 			}
  90. 			else {
  91. 				ans_3 *= (Than[dem]) ;
  92. 				ans_3 %=MOD ; 
  93. 				dem = 0 ;
  94. 			}
  95. 		//	cout << a[i].a << ' ' << a[i].b << '\n';
  96. 		}
  97. 		ans_3 *= (Than[dem]) ;
  98. 	}
  99. 	else ans_3 = 0 ;
  100. 	ans_3%=MOD ;
  101. 	cerr << ans_3 << '\n';
  102. 	ans = (Than[n] - ans_1 - ans_2 +  ans_3 )%MOD;
  103. 	while ( ans < 0 ) ans += MOD ;
  104. 	ans %= MOD ;
  105. 	cout << ans << '\n';
  106. }
  107. _nhatminh{
  108. freopen("");
  109. ios_base::sync_with_stdio(0);
  110. cin.tie(0); cout.tie(0);
  111. int q=1;
  112. // cin >> q;
  113. while (q--)
  114. 	solve();
  115. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  116. return (0);
  117. }
Success #stdin #stdout #stderr 0.01s 5824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
998244352
stderr
copy 
1
0

Time elapsed 0.006121s.
https://ideone.com/t62rNY
language:
C++14 (gcc 8.3)
created:
10 days 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!