Submission #83703

#	Time	Username	Problem	Language	Result	Execution time	Memory
83703		tfg	Candies (JOI18_candies)	C++17	0 / 100	3 ms	632 KiB

candies

#include <iostream>
#include <algorithm>
#include <vector>

const int ms = 200200;

int size[ms][2];
long long sum[ms][2], tot = 0;
int par[ms];

long long getVal(int x) {
  if(size[x][0] == size[x][1]) {
    return std::max(sum[x][0], sum[x][1]);
  } else {
    return sum[x][size[x][0] > size[x][1] ? 0 : 1];
  }
}

int totS = 0;

int getPar(int x) { return par[x] == x ? x : par[x] = getPar(par[x]); }
void makeUnion(int a, int b) {
  a = getPar(a);
  b = getPar(b);
  if(a == b) return;
  tot -= getVal(a);
  tot -= getVal(b);
  totS -= std::max(size[a][0], size[a][1]);
  totS -= std::max(size[b][0], size[b][1]);
  size[a][0] += size[b][0];
  size[a][1] += size[b][1];
  sum[a][0] += sum[b][0];
  sum[a][1] += sum[b][1];
  tot += getVal(a);
  totS += std::max(size[a][0], size[a][1]);
  par[b] = a;
}

int main() {
  std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  std::vector<int> p(n);
  for(int i = 0; i < n; i++) {
    p[i] = i;
    std::cin >> a[i];
    par[i] = -1;
  }
  std::sort(p.begin(), p.end(), [&](int p1, int p2) { return a[p1] > a[p2]; });
  std::vector<int> ans((n + 1) / 2, -1);
  for(auto x : p) {
    totS++;
    par[x] = x;
    size[x][x % 2] = 1;
    sum[x][x % 2] = a[x];
    tot += a[x];
    if(x > 0 && par[x - 1] != -1) {
      makeUnion(x, x - 1);
    }
    if(x < n - 1 && par[x + 1] != -1) {
      makeUnion(x, x + 1);
    }
    ans[totS - 1] = tot;
  }
  for(int i = 0; i < (int) ans.size(); i++) {
    std::cout << ans[i] << '\n';
  }
}

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