fork(1) download
copy 
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp> 
  18. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  19. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  20. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  21. //cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
  22.  
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25.  
  26. #define f(i,a,b) for(i=a;i<b;i++)
  27. #define rep(i,n) f(i,0,n)
  28. #define fd(i,a,b) for(i=a;i>=b;i--)
  29. #define pb push_back
  30. #define mp make_pair
  31. #define vi vector< int >
  32. #define vl vector< ll >
  33. #define ss second
  34. #define ff first
  35. #define ll long long
  36. #define pii pair< int,int >
  37. #define pll pair< ll,ll >
  38. #define sz(a) a.size()
  39. #define inf (1000*1000*1000+5)
  40. #define all(a) a.begin(),a.end()
  41. #define tri pair<int,pii>
  42. #define vii vector<pii>
  43. #define vll vector<pll>
  44. #define viii vector<tri>
  45. #define mod (1000*1000*1000+7)
  46. #define pqueue priority_queue< int >
  47. #define pdqueue priority_queue< int,vi ,greater< int > >
  48. #define flush fflush(stdout) 
  49. #define primeDEN 727999983
  50. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  51.  
  52. // find_by_order()  // order_of_key
  53. typedef tree<
  54. int,
  55. null_type,
  56. less<int>,
  57. rb_tree_tag,
  58. tree_order_statistics_node_update>
  59. ordered_set;
  60.  
  61. #define int ll
  62.  
  63. vector<vi> in(123456),out(123456);
  64. int a[123456],u[123456],v[123456],val[123456],dp[123456];
  65. vii vec;
  66.  
  67. main(){
  68.     std::ios::sync_with_stdio(false); cin.tie(NULL);
  69. 	int t;
  70. 	cin>>t;
  71. 	while(t--){
  72. 		int n,m;
  73. 		cin>>n>>m;
  74. 		int i,j;
  75. 		vec.clear();
  76. 		rep(i,n){
  77. 			cin>>a[i];
  78. 			in[i].clear();
  79. 			out[i].clear();
  80. 			vec.pb(mp(a[i],i));
  81. 		}
  82. 		sort(all(vec));
  83. 		//vec1.clear();
  84. 		rep(i,m){
  85. 			cin>>u[i]>>v[i];
  86. 			u[i]--;
  87. 			v[i]--;
  88. 			if(a[u[i]]==a[v[i]])
  89. 				continue;
  90. 			if(a[u[i]]>a[v[i]]){
  91. 				swap(u[i],v[i]);
  92. 			}
  93. 			val[i]=a[v[i]]-a[u[i]];
  94. 			in[v[i]].pb(i);
  95. 			out[u[i]].pb(i);
  96. 			dp[i]=1;
  97. 		}
  98. 		vii::iterator it;
  99. 		vii vec1;
  100. 		int gg;
  101. 		int ind;
  102. 		rep(i,n){
  103. 			gg=vec[i].ss;
  104. 			vec1.clear();
  105. 			rep(j,in[gg].size()){
  106. 				ind = in[gg][j];
  107. 				vec1.pb(mp(val[ind],dp[ind]));
  108. 			}
  109. 			sort(all(vec1));
  110. 			f(j,1,vec1.size()){
  111. 				vec1[j].ss=max(vec1[j].ss,vec1[j-1].ss);
  112. 			}
  113. 			rep(j,out[gg].size()){
  114. 				ind=out[gg][j];
  115. 				it=lower_bound(all(vec1),mp(val[ind],-10LL));
  116. 				if(it==vec1.begin())
  117. 					continue;
  118. 				it--;
  119. 				dp[ind] = max(dp[ind],it->ss+1);
  120. 			}
  121. 		}
  122. 		int ans=0;
  123. 		rep(i,m){
  124. 			ans=max(ans,dp[i]);
  125. 		}
  126. 		cout<<ans+1<<endl;
  127. 	}
  128.     return 0;   
  129. }
Runtime error #stdin #stdout 0s 28032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sCZj7X
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!