#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])));
}
if((int)vc.size()==3)
{
mp[mkp(l,r)]=cur;
si.in(mkp(l,r));
sv.in(mkp(cur,mkp(l,r)));
}
cout<<rs<<'\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
768 KB |
Output is correct |
| 2 |
Correct |
8 ms |
768 KB |
Output is correct |
| 3 |
Correct |
8 ms |
768 KB |
Output is correct |
| 4 |
Correct |
8 ms |
768 KB |
Output is correct |
| 5 |
Correct |
8 ms |
640 KB |
Output is correct |
| 6 |
Correct |
8 ms |
768 KB |
Output is correct |
| 7 |
Correct |
8 ms |
768 KB |
Output is correct |
| 8 |
Correct |
8 ms |
768 KB |
Output is correct |
| 9 |
Correct |
7 ms |
768 KB |
Output is correct |
| 10 |
Correct |
7 ms |
768 KB |
Output is correct |
| 11 |
Correct |
8 ms |
768 KB |
Output is correct |
| 12 |
Correct |
8 ms |
768 KB |
Output is correct |
| 13 |
Correct |
8 ms |
768 KB |
Output is correct |
| 14 |
Correct |
7 ms |
768 KB |
Output is correct |
| 15 |
Correct |
8 ms |
768 KB |
Output is correct |
| 16 |
Correct |
8 ms |
768 KB |
Output is correct |
| 17 |
Correct |
8 ms |
896 KB |
Output is correct |
| 18 |
Correct |
8 ms |
768 KB |
Output is correct |
| 19 |
Correct |
7 ms |
768 KB |
Output is correct |
| 20 |
Correct |
7 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
768 KB |
Output is correct |
| 2 |
Correct |
8 ms |
768 KB |
Output is correct |
| 3 |
Correct |
8 ms |
768 KB |
Output is correct |
| 4 |
Correct |
8 ms |
768 KB |
Output is correct |
| 5 |
Correct |
8 ms |
640 KB |
Output is correct |
| 6 |
Correct |
8 ms |
768 KB |
Output is correct |
| 7 |
Correct |
8 ms |
768 KB |
Output is correct |
| 8 |
Correct |
8 ms |
768 KB |
Output is correct |
| 9 |
Correct |
7 ms |
768 KB |
Output is correct |
| 10 |
Correct |
7 ms |
768 KB |
Output is correct |
| 11 |
Correct |
8 ms |
768 KB |
Output is correct |
| 12 |
Correct |
8 ms |
768 KB |
Output is correct |
| 13 |
Correct |
8 ms |
768 KB |
Output is correct |
| 14 |
Correct |
7 ms |
768 KB |
Output is correct |
| 15 |
Correct |
8 ms |
768 KB |
Output is correct |
| 16 |
Correct |
8 ms |
768 KB |
Output is correct |
| 17 |
Correct |
8 ms |
896 KB |
Output is correct |
| 18 |
Correct |
8 ms |
768 KB |
Output is correct |
| 19 |
Correct |
7 ms |
768 KB |
Output is correct |
| 20 |
Correct |
7 ms |
768 KB |
Output is correct |
| 21 |
Correct |
963 ms |
39904 KB |
Output is correct |
| 22 |
Correct |
968 ms |
39924 KB |
Output is correct |
| 23 |
Correct |
951 ms |
39928 KB |
Output is correct |
| 24 |
Correct |
453 ms |
39692 KB |
Output is correct |
| 25 |
Correct |
455 ms |
39668 KB |
Output is correct |
| 26 |
Correct |
442 ms |
39672 KB |
Output is correct |
| 27 |
Correct |
481 ms |
39948 KB |
Output is correct |
| 28 |
Correct |
487 ms |
39928 KB |
Output is correct |
| 29 |
Correct |
480 ms |
39800 KB |
Output is correct |
| 30 |
Correct |
492 ms |
39928 KB |
Output is correct |
| 31 |
Correct |
497 ms |
39800 KB |
Output is correct |
| 32 |
Correct |
495 ms |
39800 KB |
Output is correct |
| 33 |
Correct |
648 ms |
39804 KB |
Output is correct |
| 34 |
Correct |
655 ms |
39672 KB |
Output is correct |
| 35 |
Correct |
662 ms |
39672 KB |
Output is correct |
| 36 |
Correct |
928 ms |
40184 KB |
Output is correct |
| 37 |
Correct |
939 ms |
39960 KB |
Output is correct |
| 38 |
Correct |
903 ms |
40020 KB |
Output is correct |
| 39 |
Correct |
452 ms |
39672 KB |
Output is correct |
| 40 |
Correct |
445 ms |
39672 KB |
Output is correct |
| 41 |
Correct |
443 ms |
39788 KB |
Output is correct |
| 42 |
Correct |
469 ms |
39800 KB |
Output is correct |
| 43 |
Correct |
465 ms |
39800 KB |
Output is correct |
| 44 |
Correct |
480 ms |
40056 KB |
Output is correct |
| 45 |
Correct |
488 ms |
39848 KB |
Output is correct |
| 46 |
Correct |
491 ms |
40092 KB |
Output is correct |
| 47 |
Correct |
491 ms |
39792 KB |
Output is correct |
| 48 |
Correct |
650 ms |
39588 KB |
Output is correct |
| 49 |
Correct |
641 ms |
39544 KB |
Output is correct |
| 50 |
Correct |
681 ms |
39656 KB |
Output is correct |
