Submission #1148818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148818		mychecksedad	Candies (JOI18_candies)	C++17	100 / 100	392 ms	31832 KiB

candies

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n;
ll a[N], pref[N][2];

ll get_sum(int l, int r){
  if(l%2) return pref[r][0] - (l == 1 ? 0ll : pref[l - 2][0]);
  return pref[r][1] - pref[l - 2][1];
}

void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  pref[0][0] = 0;
  pref[1][0] = a[1];
  for(int i = 3; i <= n; i += 2){
    pref[i][0] = pref[i - 2][0] + a[i];
  }
  for(int i = 2; i <= n; i += 2){
    pref[i][1] = pref[i - 2][1] + a[i];
  }

  set<pii> S;
  priority_queue<array<ll, 3>> Q;
  map<pii, bool> in_qu;
  for(int i = 1; i <= n; ++i){
    Q.push({a[i], i, i});
    in_qu[{i, i}] = 1;
  }
  ll ans = 0;
  for(int i = 1; i <= (n+1)/2; ++i){
    auto [val, l, r] = Q.top(); Q.pop();
    // cout << val << ' '  << l << ' ' << r << '\n';
    if(!in_qu[{l, r}]){
      --i;
      continue;
    }
    ans += val;
    S.erase({l-1, l-1});
    S.erase({r+1, r+1});
    in_qu[{l-1, l-1}] = 0;
    in_qu[{r+1, r+1}] = 0;
    cout << ans << '\n';
    if(l < r)
      S.erase(pii{l + 1, r - 1});
    auto it = S.lower_bound(pii{r, -1});
    if(it != S.end()){
      if(it->ff == r+2){
        r = it->ss;
        in_qu[{it->ff - 1, it->ss + 1}] = 0;
        S.erase(it);
      }
    }
    it = S.lower_bound(pii{r, -1});
    if(it != S.begin()){
      it = prev(it);
      if(it->ss == l-2){
        l = it->ff;
        in_qu[{it->ff - 1, it->ss + 1}] = 0;
        S.erase(it);
      }
    }
    if(l - 1 >= 1 && r + 1 <= n){
      Q.push({get_sum(l - 1, r + 1) - get_sum(l, r), l - 1, r + 1});
      in_qu[{l - 1, r + 1}] = 1;
    }
    S.insert({l, r});
    // for(auto [x, y]: S) cout << x << ' ' << y << '\n';
    // en;
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92