oj.uz

Submission #83703

# Submission time Handle Problem Language Result Execution time Memory
83703 2018-11-10T01:51:13 Z tfg Candies (JOI18_candies) C++17
0 / 100
 3 ms 632 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -