oj.uz

Submission #465725

# Submission time Handle Problem Language Result Execution time Memory
465725 2021-08-16T17:12:51 Z alexxela12345 Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 25436 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct mdata {
  vector<pair<int, int>> arr;

  int size();
  int get(int);
};

int mdata::size() { return arr.size(); }

int mdata::get(int i) { return arr[i].second; }

void erase(mdata &mda, int i, int x) {
  mda.arr.erase(find(mda.arr.begin(), mda.arr.end(), pair<int, int>{i, x}));
}

void add(mdata &mda, int i, int x) {
  mda.arr.push_back({i, x});
  sort(mda.arr.begin(), mda.arr.end());
}

int get_fst_diff(mdata &mda, int mx_diff) {
  // returns index to first arrow after which everything contains in a segment of size mx
  int cur = 0;
  int mn = 0, mx = 0;
  for (int i = mda.size() - 1; i >= 0; i--) {
    int a = mda.get(i);
    cur += a;
    mn = min(mn, cur);
    mx = max(mx, cur);
    if (mx - mn >= mx_diff) {
      return i + 1;
    }
  }
  return 0;
}

int get_min_suf(mdata &mda, int fst) {
  int cur = 0;
  int mn = 0;
  for (int i = mda.size() - 1; i >= fst; i--) {
    cur += mda.get(i);
    if (cur < mn) {
      mn = cur;
    }
  }
  return mn;
}


int get_max_suf(mdata &mda, int fst) {
  int cur = 0;
  int mn = 0;
  for (int i = mda.size() - 1; i >= fst; i--) {
    cur += mda.get(i);
    if (cur > mn) {
      mn = cur;
    }
  }
  return mn;
}

int get_ans(mdata &mda, int mx) {
  int fst = get_fst_diff(mda, mx);
  int start = 0;
  if (fst == 0) {
    start = 0;
  } else {
    int a = mda.get(fst - 1);
    if (a > 0) {
      start = mx;
    } else {
      start = 0;
    }
  }
  if (start == 0) {
    int ans = get_max_suf(mda, fst);
    return start + ans;
  } else {
    int ans = get_min_suf(mda, fst);
    return start + ans;
  }
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
				    vector<int> r, vector<int> v) {
  int n = c.size();
  vector<vector<int>> add_evs(n + 1), rem_evs(n + 1);
  for (int i = 0; i < (int) l.size(); i++) {
    add_evs[l[i]].push_back(i);
    rem_evs[r[i] + 1].push_back(i);
  }
  mdata mda;
  vector<int> ans;
  ans.reserve(n);
  for (int i = 0; i < n; i++) {
    for (int el : rem_evs[i]) {
      erase(mda, el, v[el]);
    }
    for (int el : add_evs[i]) {
      add(mda, el, v[el]);
    }
    ans.push_back(get_ans(mda, c[i]));
  }
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 41 ms 400 KB Output is correct
4 Correct 40 ms 332 KB Output is correct
5 Correct 55 ms 572 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 25436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 5020 ms 9676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Execution timed out 5098 ms 8740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 41 ms 400 KB Output is correct
4 Correct 40 ms 332 KB Output is correct
5 Correct 55 ms 572 KB Output is correct
6 Execution timed out 5029 ms 25436 KB Time limit exceeded
7 Halted 0 ms 0 KB -