Submission #1264317

#TimeUsernameProblemLanguageResultExecution timeMemory
1264317nguyenhuythachCandies (JOI18_candies)C++20
8 / 100
11 ms1864 KiB
#include<bits/stdc++.h> #include<algorithm> #include<random> #include<chrono> #include<cstdlib> #include<ctime> #include<numeric> #include<vector> #include<stack> #include<map> #include<set> #include<queue> #include<iomanip> #define int long long #define ll long long #define L LLONG_MAX #define fi first #define se second #define pii pair<int,int> #define sz(a) ((int)a.size()) #define FOR(i,j,k) for(int i=j;i<=k;i++) #define REP(i,k,j) for(int i=k;i>=j;i--) #define FORD(i,a) for(auto i:a) #define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(l,r) ((l)+(rng()%(r-l+1))) using namespace std; const int nmax=2e5+1; int n; int a[nmax],lf[nmax],rt[nmax],st[nmax]; priority_queue<pii,vector<pii>> pq; void input() { cin >> n; FOR(i,1,n) cin >> a[i]; a[0]=a[n+1]=-1e18; FOR(i,1,n) { lf[i]=i-1; rt[i]=i+1; pq.push({a[i],i}); } } void solve() { int ans=0; FOR(i,1,(n+1)/2) { while(!pq.empty() && st[pq.top().se]) pq.pop(); pii save=pq.top(); pq.pop(); ans+=save.fi; cout << ans << '\n'; a[save.se]=a[lf[save.se]]+a[rt[save.se]]-a[save.se]; pq.push({a[save.se],save.se}); st[lf[save.se]]=1; st[rt[save.se]]=1; lf[save.se]=lf[lf[save.se]]; rt[save.se]=rt[rt[save.se]]; lf[rt[save.se]]=save.se; rt[lf[save.se]]=save.se; } } signed main() { //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...