Submission #369705

#	Time	Username	Problem	Language	Result	Execution time	Memory
369705		Mamnoon_Siam	Candies (JOI18_candies)	C++17	100 / 100	785 ms	19568 KiB

candies

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ii = pair<ll, ll>;
const int maxn = 2e5 + 5;

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
int N;
ll a[maxn];
 
struct node {
  ll val;
  node *l, *r;
  node () {
    val = 0;
    l = r = NULL;
  }
};
 
using llp = pair<ll, node*>;
 
multiset<ii> Q;
int le[maxn], ri[maxn];
 
int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  cin >> N;
  for(int i = 1; i <= N; i++) {
    cin >> a[i];
    le[i] = i-1, ri[i] = i+1;
    Q.insert(ii(a[i], i));
  }
  a[0] = -1e18, a[N+1] = -1e18;
  /*for(int i = 1; i <= N; i++) {
    node *now = new node();
    now -> val = a[i];
    now -> l = prev;
    if(prev) now -> l -> r = now;
    Q.insert(llp(a[i], now));
    prev = now;
  }*/
  ll ans = 0;
  for(int i = 1; i <= (N - 1) / 2 + 1; i++) {
    
    // take best
    int best = (int)Q.rbegin() -> second;
    Q.erase(--Q.end());
    // update answer
    // ans += best -> val;
    ans += a[best];

    // create virtual elem
    // node *now = new node();
    // now -> val = -best -> val;

    a[best] = -a[best];

    int l = le[best];
    int r = ri[best];


    if(true) {
      Q.erase(ii(a[l], l));
      le[best] = le[l];
      a[best] += a[l];
    }
    if(true) {
      Q.erase(ii(a[r], r));
      ri[best] = ri[r];
      a[best] += a[r];
    }

    if(le[best]) {
      ri[le[best]] = best;
    }
    if(ri[best] <= N) {
      le[ri[best]] = best;
    }


    /*if(best -> l) {
      Q.erase(llp(best -> l -> val, best -> l));
      now -> val += best -> l -> val;
      now -> l = best -> l -> l;
      // delete(best -> l);
    } else {
      flag = 0;
    }
    if(best -> r) {
      Q.erase(llp(best -> r -> val, best -> r));
      now -> val += best -> r -> val;
      now -> r = best -> r -> r;
      // delete(best -> r);
    } else {
      flag = 0;
    }
    if(now -> l) now -> l -> r = now;
    if(now -> r) now -> r -> l = now;*/
    Q.insert(ii(a[best], best));
    cout << ans << endl;
  }
  return 0;
}

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