tanuj208

CF Round 622 C2

Feb 23rd, 2020
49
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //#pragma GCC optimize("Ofast")
  5. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. //#pragma GCC optimize("unroll-loops")
  7.  
  8. #define pb push_back
  9. #define mp make_pair
  10. #define sz(a) (ll)(a).size()
  11. #define all(a) a.begin(), a.end()
  12. #define ff first
  13. #define ss second
  14. #define endl "\n"
  15.  
  16. #include <ext/pb_ds/assoc_container.hpp> // Common file
  17. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  18.  
  19. using namespace __gnu_pbds;
  20. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> pbds;
  21. //K-th smallest
  22. //cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;
  23. //NO OF ELEMENTS < X
  24. //cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
  25.  
  26. // priority_queue <ll,vector<ll>,greater<ll> > p;
  27.  
  28. typedef long long ll;
  29. typedef pair<ll,ll> pii;
  30.  
  31. ll mod=1000000007;
  32.  
  33. ll power(ll x, ll y)
  34. {
  35.     ll temp;
  36.     if( y == 0)
  37.         return 1;
  38.     temp = power(x, y/2);
  39.     if (y%2 == 0)
  40.         return (temp*temp)%mod;
  41.     else
  42.         return (((x*temp)%mod)*temp)%mod;
  43. }
  44.  
  45. int main()
  46. {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.     cout.tie(NULL);
  50.     ll n;
  51.     cin>>n;
  52.     vector<ll> a;
  53.     ll i;
  54.     for(i=0;i<n;i++)
  55.     {
  56.         ll val;
  57.         cin>>val;
  58.         a.pb(val);
  59.     }
  60.     set<pii, greater<pii>> ht;
  61.     ht.insert(mp(a[0], 1));
  62.     vector<ll> arr1(n+5, 0), arr2(n+5,0);
  63.     arr1[0]=a[0];
  64.     for(i=1;i<n;i++)
  65.     {
  66.         ll cnt=0;
  67.         ll sub=0;
  68.         while(!ht.empty())
  69.         {
  70.             ll tmp = ht.begin()->first;
  71.             ll cc = ht.begin()->ss;
  72.             if(tmp>a[i])
  73.             {
  74.                 ht.erase(ht.begin());
  75.                 cnt+=cc;
  76.                 sub+=(tmp*cc);
  77.             }
  78.             else
  79.                 break;
  80.         }
  81.         ht.insert(mp(a[i], cnt+1));
  82.         arr1[i]=arr1[i-1]-sub+a[i]*(cnt+1);
  83.     }
  84.  
  85.     ht.clear();
  86.     ht.insert(mp(a[n-1], 1));
  87.     arr2[n-1]=a[n-1];
  88.     for(i=n-2;i>=0;i--)
  89.     {
  90.         ll cnt=0;
  91.         ll sub=0;
  92.         while(!ht.empty())
  93.         {
  94.             ll tmp = ht.begin()->first;
  95.             ll cc = ht.begin()->ss;
  96.             if(tmp>a[i])
  97.             {
  98.                 ht.erase(ht.begin());
  99.                 cnt+=cc;
  100.                 sub+=(tmp*cc);
  101.             }
  102.             else
  103.                 break;
  104.         }
  105.         ht.insert(mp(a[i], cnt+1));
  106.         arr2[i]=arr2[i+1]-sub+a[i]*(cnt+1);
  107.     }
  108.     // for(i=0;i<n;i++)
  109.     //  cout<<arr1[i]<<" ";
  110.     // cout<<endl;
  111.     // for(i=0;i<n;i++)
  112.     //  cout<<arr2[i]<<" ";
  113.     // cout<<endl;
  114.     ll mx=0;
  115.     ll idx;
  116.     for(i=0;i<n;i++)
  117.     {
  118.         if(mx < arr1[i]+arr2[i]-a[i])
  119.         {
  120.             mx=arr1[i]+arr2[i]-a[i];
  121.             idx=i;
  122.         }
  123.     }
  124.  
  125. // cout<<mx<<" "<<idx<<endl;
  126.  
  127.     vector<ll> ans(n+5);
  128.     ans[idx]=a[idx];
  129.     ll curmax=a[idx];
  130.     for(i=idx-1;i>=0;i--)
  131.     {
  132.         curmax=min(curmax, a[i]);
  133.         ans[i]=curmax;
  134.     }
  135.     curmax=a[idx];
  136.     for(i=idx+1;i<n;i++)
  137.     {
  138.         curmax=min(curmax, a[i]);
  139.         ans[i]=curmax;
  140.     }
  141.     for(i=0;i<n;i++)
  142.         cout<<ans[i]<<" ";
  143.     cout<<endl;
  144.     return 0;
  145. }
RAW Paste Data