//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const ll mod=1e9+7;
using namespace std;
int n,i,j,l,r;
pair<int,int>pr;
set<pair<ll,pair<int,int> > >sv;
set<pair<ll,pair<int,int> > >::iterator iv;
set<pair<int,int> >si;
set<pair<int,int> >::iterator ii;
vector<pair<int,int> >vc;
map<pair<int,int>,ll>mp;
ll rs,cur,a[nmax];
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++)
{
sv.in(mkp(a[i],mkp(i,i)));
si.in(mkp(i,i));
mp[mkp(i,i)]=a[i];
}
for(i=1;i<=(n+1)/2;i++)
{
iv=(--sv.end());
rs+=iv->fr;
pr=iv->sc;
ii=si.fd(pr);
vc.clear();
if(ii!=si.begin())
{
ii--;
vc.pb(*ii);
ii++;
}
vc.pb(*ii);
ii++;
if(ii!=si.end())vc.pb(*ii);
cur=0,l=inf,r=0;
for(j=0;j<(int)vc.size();j++)
{
l=min(l,vc[j].fr);
r=max(r,vc[j].sc);
if(vc[j]!=pr)cur+=mp[vc[j]];
else cur-=mp[vc[j]];
si.er(si.fd(vc[j]));
sv.er(sv.fd(mkp(mp[vc[j]],vc[j])));
}
mp[mkp(l,r)]=cur;
si.in(mkp(l,r));
sv.in(mkp(cur,mkp(l,r)));
cout<<rs<<endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
