oj.uz

답안 #592038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592038 2022-07-08T12:12:02 Z lorenzoferrari 사탕 분배 (IOI21_candies) C++17
38 / 100
 546 ms 33596 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;

const LL Nan = 1e18;

struct Segment {
  struct node {
    LL mn;
    LL mx;
    LL lSum;
    LL lSet;
    node(LL x = 0) : mn(x), mx(x), lSum(0), lSet(Nan) {}
    node(LL x, LL y) : mn(x), mx(y), lSum(0), lSet(Nan) {}
  };
  node join(const node& a, const node& b) {
    return node(min(a.mn, b.mn), max(a.mx, b.mx));
  }
  int n;
  vector<node> t;
  Segment(int _n) {
    for (n = 1; n < _n; n <<= 1);
    t.resize(2 * n);
  }
  void applySum(int i, LL x) {
    if (t[i].lSet != Nan) {
      t[i].lSet += x;
    } else {
      t[i].lSum += x;
    }
  }
  void applySet(int i, LL x) {
    t[i].lSum = 0;
    t[i].lSet = x;
  }
  void prop(int i) {
    // lSum and lSet are never both set
    if (t[i].lSum) {
      t[i].mn += t[i].lSum;
      t[i].mx += t[i].lSum;
      if (i < n) {
        applySum(2*i  , t[i].lSum);
        applySum(2*i+1, t[i].lSum);
      }
      t[i].lSum = 0;
    } else if (t[i].lSet != Nan) {
      t[i].mn = t[i].mx = t[i].lSet;
      if (i < n) {
        applySet(2*i  , t[i].lSet);
        applySet(2*i+1, t[i].lSet);
      }
      t[i].lSet = Nan;
    }
  }
  void add(int i, int l, int r, int a, int b, LL x) {
    prop(i);
    if (r <= a || b <= l) return;
    if (l <= a && b <= r) {
      applySum(i, x);
      prop(i);
    } else {
      int m = (a+b) / 2;
      add(2*i  , l, r, a, m, x);
      add(2*i+1, l, r, m, b, x);
      t[i] = join(t[2*i], t[2*i+1]);
    }
  }
  void setmax(int i, int l, int r, int a, int b, LL x) {
    prop(i);
    if (r <= a || b <= l || t[i].mx <= x) return;
    if (l <= a && b <= r && t[i].mx == t[i].mn) {
      applySet(i, x);
      prop(i);
    } else {
      int m = (a+b) / 2;
      setmax(2*i  , l, r, a, m, x);
      setmax(2*i+1, l, r, m, b, x);
      t[i] = join(t[2*i], t[2*i+1]);
    }
    assert(t[i].mx <= x);
  }
  void setmin(int i, int l, int r, int a, int b, LL x) {
    prop(i);
    if (r <= a || b <= l || t[i].mn >= x) return;
    if (l <= a && b <= r && t[i].mx == t[i].mn) {
      applySet(i, x);
      prop(i);
    } else {
      int m = (a+b) / 2;
      setmin(2*i  , l, r, a, m, x);
      setmin(2*i+1, l, r, m, b, x);
      t[i] = join(t[2*i], t[2*i+1]);
    }
    assert(t[i].mn >= x);
  }
  void add(int l, int r, LL x) { add(1, l, r+1, 0, n, x); }
  void setmax(int l, int r, LL x) { setmax(1, l, r+1, 0, n, x); }
  void setmin(int l, int r, LL x) { setmin(1, l, r+1, 0, n, x); }
  void propall() {
    for (int i = 1; i < 2*n; ++i) {
      prop(i);
    }
  }
  int get(int p) {
    /*
    vector<int> a;
    for (int i = p + n; i > 0; i >>= 1) a.push_back(i);
    for (int i = int(a.size())-1; i >= 0; --i) prop(a[i]);
    */
    assert(t[p+n].mn == t[p+n].mx);
    return t[p+n].mn;
  }
};

vi c_equal(vi c, vi l, vi r, vi v) {
  int n = c.size();
  Segment st(n);
  for (int i = 0; i < int(l.size()); ++i) {
    st.add(l[i], r[i], v[i]);
    if (v[i] > 0) st.setmax(l[i], r[i], c[0]);
    else st.setmin(l[i], r[i], 0);
  }
  st.propall();
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    s[i] = st.get(i);
  }
  return s;
}

vi brute_force(vi c, vi l, vi r, vi v) {
  int n = c.size();
  vector<int> s(n, 0);
  for (int i = 0; i < int(l.size()); ++i) {
    for (int j = l[i]; j <= r[i]; ++j) {
      if (v[i] > 0) s[j] = min(s[j] + v[i], c[j]);
      if (v[i] < 0) s[j] = max(s[j] + v[i], 0);
    }
  }
  return s;
}

vi v_positive(vi c, vi l, vi r, vi v) {
  int n = c.size();
  vector<LL> prf(n+1);
  for (int i = 0; i < int(l.size()); ++i) {
    prf[l[i]] += v[i];
    prf[r[i] + 1] -= v[i];
  }
  for (int i = 1; i < n; ++i) {
    prf[i] += prf[i - 1];
  }
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    s[i] = min((LL)c[i], prf[i]);
  }
  return s;
}

vi distribute_candies(vi c, vi l, vi r, vi v) {
  int n = c.size();
  int q = l.size();
  if (n <= 2000 && q <= 2000) {
    return brute_force(c, l, r, v);
  } else if (*min_element(v.begin(), v.end()) > 0) {
    return v_positive(c, l, r, v);
  } else if (*min_element(c.begin(), c.end()) == *max_element(c.begin(), c.end())) {
    return c_equal(c, l, r, v);
  }
  return vector<int>(n, 0);
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 11964 KB Output is correct
2 Correct 95 ms 12000 KB Output is correct
3 Correct 99 ms 12000 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 135 ms 7520 KB Output is correct
3 Correct 59 ms 22068 KB Output is correct
4 Correct 409 ms 32816 KB Output is correct
5 Correct 403 ms 33232 KB Output is correct
6 Correct 546 ms 33596 KB Output is correct
7 Correct 455 ms 32936 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 46 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 100 ms 11964 KB Output is correct
7 Correct 95 ms 12000 KB Output is correct
8 Correct 99 ms 12000 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 135 ms 7520 KB Output is correct
11 Correct 59 ms 22068 KB Output is correct
12 Correct 409 ms 32816 KB Output is correct
13 Correct 403 ms 33232 KB Output is correct
14 Correct 546 ms 33596 KB Output is correct
15 Correct 455 ms 32936 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 46 ms 4972 KB Output isn't correct
19 Halted 0 ms 0 KB -