제출 #883594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883594		nguyentunglam	사탕 분배 (IOI21_candies)	C++17	100 / 100	4219 ms	59312 KiB

candies

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
using namespace std;

const int N = 2e5 + 10;

int L[N], R[N], last[N], mx[N], mn[N];

array<long long, 3> T[N << 2];

array<long long, 3> zero = {0, 0, 0};

vector<int> query[N];

void add (array<long long, 3> &a, array<long long, 3> b) {
  a[1] = min(a[1], a[0] + b[1]);
  a[2] = max(a[2], a[0] + b[2]);
  a[0] += b[0];
}

void push(int s, int l, int r) {
  if (l == r || T[s] == zero) return;
  add(T[s << 1], T[s]);
  add(T[s << 1 | 1], T[s]);
  T[s] = zero;
}

void up(int s, int l, int r, int from, int to, int val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    add(T[s], {val, val, val});
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
}

array<long long, 3> get(int s, int l, int r, int pos) {
  push(s, l, r);
  if (l == r)  return T[s];
  int mid = l + r >> 1;
  if (pos <= mid) return get(s << 1, l, mid, pos);
  return get(s << 1 | 1, mid + 1, r, pos);
}

vector<int> distribute_candies (vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  int n = c.size();
  vector<int> p(n);

  l.insert(l.begin(), 0);
  l.insert(l.begin(), 0);

  r.insert(r.begin(), n - 1);
  r.insert(r.begin(), n - 1);

  v.insert(v.begin(), -2e9);
  v.insert(v.begin(), 2e9);

  int q = v.size();

  for(int i = 0; i < n; i++) {
    L[i] = 0; R[i] = q - 1;
  }

  for(int loop = 1; loop <= 20; loop++) {
    bool valid = 0;
    for(int i = 0; i < n; i++) if (L[i] <= R[i]) {
      query[L[i] + R[i] >> 1].push_back(i);
      valid = 1;
    }
    if (!valid) break;


    for(int i = q - 1; i >= 0; i--) {
      for(int &j : query[i]) {
        array<ll, 3> tmp = get(1, 0, n - 1, j);
        if (tmp[2] - tmp[1] <= c[j]) {
          R[j] = i - 1;
          last[j] = i;
          mn[j] = tmp[1];
          mx[j] = tmp[2];
        } else L[j] = i + 1;
      } query[i].clear();
      up(1, 0, n - 1, l[i], r[i], -v[i]);
    }

    for(int i = 1; i <= 4 * n; i++) T[i] = zero;
  }

  for(int i = 0; i < n; i++) {
    int j = last[i];
    if (v[j] > 0) p[i] = c[i] - mx[i];
    else p[i] = -mn[i];
  }

  return p;
}


#ifdef ngu
  int32_t main() {

    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);

    int n; cin >> n;

    vector<int> c(n);

    for(int i = 0; i < n; i++) cin >> c[i];

    int q; cin >> q;

    vector<int> l(q), r(q), v(q);

    for(int i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];

    vector<int> ans = distribute_candies(c, l, r, v);

    for(int &j : ans) cout << j << " ";
  }
#endif // ngu

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'void up(int, int, int, int, int, int)':
candies.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid = l + r >> 1;
      |             ~~^~~
candies.cpp: In function 'std::array<long long int, 3> get(int, int, int, int)':
candies.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |       query[L[i] + R[i] >> 1].push_back(i);
      |             ~~~~~^~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33