fork download
  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
stdin
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
94
78
78
77
39
39
18
18
14
6
5
17
5
9
9
5
0