fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1e6;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20.  
  21.  
  22. multiset < ll > st ;
  23. int a[maxn +3 ] ;
  24. int b[maxn + 3] ;
  25. bool check[maxn + 3] ;
  26. ll ans[maxn + 3]; 
  27. bool haved[maxn+3] ;
  28. ll s[maxn+3] ;
  29. int f[maxn+3];
  30. int n ;
  31. int find_root ( int u ){
  32. 	return ( f[u] < 0 )? ( u) : f[u] = find_root ( f[u] ) ;
  33. }
  34. void unit ( int x , int y ) {
  35. 	x = find_root ( x ) ;
  36. 	y = find_root ( y ) ;
  37. 	if ( x == y ) return ;
  38. 	if ( f[x] > f[y]) swap( x ,y ) ;
  39. 	f[x] += f[y] ;
  40. 	f[y] = x ; 
  41. 	st.erase( s[y ] ) ;
  42. 	st.insert ( s[x] += s[y]) ;
  43. 	s[y] = 0 ;
  44. }
  45. void add ( int i ) {
  46. 	if ( haved[i]) return ;
  47. 	haved[i] = 1 ;
  48. 	s[i]  = a[i] ;
  49. 	st.insert ( s[i] ) ;
  50. 	if(i>1&&!check[i-1]) unit(i,i-1);
  51.     if(i<n&&!check[i+1]) unit(i,i+1);
  52. } int k ;
  53. void input(){
  54. 	memset ( f , -1 , sizeof ( f));
  55. 	cin >> n >> k ;
  56. 	for ( int i = 1 ; i <= n ; i ++ ){
  57. 		cin >> a[i];
  58. 	}
  59. 	FOR ( i , 1 , k ) {
  60. 		cin >> b[i] ;
  61. 		check[b[i]] = 1 ;
  62. 	}
  63.  
  64. 	FOR ( i , 1 , n ) {
  65. 		if (!check[i]) {
  66. 				s[i] = a[i] ;
  67. 				haved[i] = 1 ;
  68. 				st.insert ( s[i] ) ;
  69. 			if (!check[i-1] && i > 1) {
  70. 				unit ( i , i -1 ) ;
  71. 			}
  72. 		}	
  73. 	}
  74. 	for (int i = k ; i >= 1 ; i -- ) {
  75. 		ans[i] = *st.rbegin() ;
  76. 		check[b[i]] = 0 ;
  77. 		add ( b[i] ) ;
  78. 	}
  79. 	for ( int i = 1 ; i <= k ; i ++ ){
  80. 		cout << ans[i] << '\n' ;
  81. 	}
  82.  
  83. }
  84. #define name "TASK" 
  85. int main(){
  86.     fast 
  87.     if(fopen(name".INP","r")) {
  88.         freopen (name".INP","r",stdin);
  89.         freopen (name".OUT","w",stdout);
  90.     }
  91.     input() ;
  92.  
  93.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  94.     return(0) ;
  95. }
  96.  
Success #stdin #stdout #stderr 0.01s 8440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
TIME: = 0.006217
https://ideone.com/fyt5DD
language:
C++14 (gcc 8.3)
created:
12 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!