Submission #1127518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127518		duong3982	Candies (JOI18_candies)	C++20	100 / 100	104 ms	10024 KiB

candies

#include <bits/stdc++.h>

using namespace std;

#define             fi  first
#define             se  second
#define           left  ___left___
#define          right  ___right___
#define   scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define  print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
  #include "debug.h"
#else
  #define debug(...)
#endif

const int N = 2e5 + 5;

int n, k;
int lab[N], lt[N], rt[N], a[N];
bool del[N];
long long val[N];

int find(int u) {
  assert(u);
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void mrg(int u, int v) {
  if ((u = find(u)) == (v = find(v))) {
    return;
  }
  if (lab[u] > lab[v]) {
    swap(u, v);
  }
  lab[u] += lab[v];
  lab[v] = u;
  del[u] |= del[v];
  lt[u] = min(lt[u], lt[v]);
  rt[u] = max(rt[u], rt[v]);
}

int getL(int i) {
  return lt[find(i)];
}

int getR(int i) {
  return rt[find(i)];
}

long long qryVal(int i) {
  return val[find(i)];
}

void process(void) {
  cin >> n;
  using T = tuple<long long, int, int>;
  priority_queue<T> pq;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    lab[i] = -1;
    val[i] = a[i];
    lt[i] = rt[i] = i;
    pq.push({val[i], i, i});
  }
  long long res = 0;
  for (int i = 0; i < (n + 1) / 2; ++i) {
    while (1) {
      assert(pq.size());
      long long x;
      int l, r;
      tie(x, l, r) = pq.top();
      pq.pop();
      if (l ^ getL(l) || r ^ getR(r)) {
        continue;
      }
      del[find(l)] |= l == 1 || r == n;
      res += x;
      long long nxt = -qryVal(l);
      if (l > 1) {
        nxt += qryVal(l - 1);
        mrg(l, l - 1);
      }
      if (r < n) {
        nxt += qryVal(r + 1);
        mrg(r, r + 1);
      }
      int id = find(l);
      if (!del[id]) {
        val[id] = nxt;
        pq.push({val[id], lt[id], rt[id]});
      }
      break;
    }
    cout << res << "\n";
  }
}

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  file("DAN");
  // int t; cin >> t; while (t--)
  process();
  return (0^0);
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:11:62: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:102:3: note: in expansion of macro 'file'
  102 |   file("DAN");
      |   ^~~~
candies.cpp:11:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:102:3: note: in expansion of macro 'file'
  102 |   file("DAN");
      |   ^~~~

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