fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 1000000007
  4.  
  5. long long pre[200005];
  6. long long sum(int a,int b) {
  7.  
  8. 	return pre[b] - pre[a-1];
  9. }
  10.  
  11. set<pair<int,int> > st;
  12.  
  13. set<pair<int,int> > :: iterator it;
  14. multiset<long long> mset;
  15. multiset<long long> :: iterator it2;
  16. int main() {
  17.  
  18. 	ios_base::sync_with_stdio(0);cin.tie(0);
  19. 	pre[0] = 0;
  20. 	long long n,x;
  21. 	cin>>n;
  22. 	for(int i=1 ;i<=n;i++) {
  23. 		cin>>x;
  24. 		pre[i] = pre[i-1] + x;
  25. 	}
  26. 	st.insert(make_pair(1,n));
  27. 	mset.insert(sum(1,n));
  28. 	pair<int,int> p,p1,p2;
  29.  
  30. 	for(int i=0;i<n;i++) {
  31. 		cin>>x;
  32. 		it = st.upper_bound(make_pair(x,1e9));
  33. 		it -- ;
  34. 		p = *it;
  35. 		//cout<<"df";
  36. 		st.erase(it);
  37. 		mset.erase(sum(p.first,p.second));
  38. 		//if(p.first == p.second) continue;
  39. 		//p1 = make_pair(p.first,x-1);
  40. 		//p2 = make_pair(x+1,p.second);
  41. 		//if(x-1>=p.first) {
  42. 			if(x-1 >= p.first)
  43. 			st.insert(make_pair(p.first,x-1));
  44. 			mset.insert(sum(p.first,x-1));
  45. 		//} else mset.insert(0);
  46. 		//if(x+1<=p.second) {
  47. 			if(x+1 <= p.second)
  48. 			st.insert(make_pair(x+1,p.second));
  49. 			mset.insert(sum(x+1,p.second));
  50. 		//}// else mset.insert(0);
  51. 		it2 = mset.end();
  52. 		it2 -- ;
  53. 		cout<< *it2<<endl;
  54. 	}
  55.  
  56. 	return 0;		
  57. }
  58.  
Success #stdin #stdout 0s 5028KB
comments (?)
stdin
copy 
17
12 9 17 5 0 6 5 1 3 1 17 17 2 14 5 1 17
3 7 5 8 12 9 15 13 11 14 6 16 17 1 10 2 4
stdout
copy 
94
78
78
77
39
39
18
18
14
6
5
17
5
9
9
5
0
https://ideone.com/08V4dG
language:
C++ (gcc 8.3)
created:
7 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!