제출 #1126597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126597		VinhLuu	사탕 분배 (IOI21_candies)	C++20	100 / 100	350 ms	43784 KiB

candies

#include <bits/stdc++.h>
//#define ll long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

//#define lpv

#ifndef lpv
#include "candies.h"
#endif // lpv

typedef pair<ll,ll> pii;
const ll N = 2e5 + 5;

ll n, q, h[N], a[N], L[N], R[N], C[N], mi[N << 2], mx[N << 2], lz[N << 2], st[N << 2];
vector<ll> open[N], _close[N];

void update(ll i,ll l,ll r,ll u,ll x) {
  if(l > r || r < u || u < l) return;
  if(l == r) {
    st[i] = x;
    mx[i] = max(0ll, x);
    mi[i] = min(0ll, x);
    return;
  }
  ll mid = (l + r) / 2;
  update(i << 1, l, mid, u, x);
  update(i << 1|1, mid + 1, r, u, x);
  mi[i] = min(mi[i << 1], st[i << 1] + mi[i << 1|1]);
  mx[i] = max(mx[i << 1], st[i << 1] + mx[i << 1|1]);
  st[i] = st[i << 1] + st[i << 1|1];
}

ll query(ll i,ll l,ll r,ll c) {
  if(l == r) return min(max(0ll, st[i]), c);
  ll mid = (l + r) / 2;

  if(mx[i << 1|1] - mi[i << 1|1] > c) return query(i << 1|1, mid + 1, r, c);
  ll ret = query(i << 1, l, mid, c);
  if(ret + mx[i << 1|1] > c) return c - (mx[i << 1|1] - st[i << 1|1]);
  if(ret + mi[i << 1|1] < 0) return st[i << 1|1] - mi[i << 1|1];
  return ret + st[i << 1|1];
}


std::vector<int> distribute_candies(std::vector<int> _c, std::vector<int> _l,
                                    std::vector<int> _r, std::vector<int> _v) {
  n = _c.size();

  for(ll i = 1; i <= n; i ++) a[i] = _c[i - 1];
  q = (ll)_l.size();

  for(ll i = 1; i <= q; i ++) L[i] = _l[i - 1] + 1, R[i] = _r[i - 1] + 1, C[i] = _v[i - 1];

  vector<int> kq;

  for(ll i = 1; i <= q; i ++) {
    open[L[i]].push_back(i);
    _close[R[i] + 1].push_back(i);
  }

  for(ll i = 1; i <= n; i ++) {
    for(auto j : open[i]) {
      update(1, 1, q, j, C[j]);
    }
    for(auto j : _close[i]) {
      update(1, 1, q, j, 0);
    }
    kq.push_back({query(1, 1, q, a[i])});
  }

  return kq;
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  ll _n;
  cin >> _n;
  std::vector<int> _c(_n);
  for(ll i = 0; i < _n; ++i) {
    cin >> _c[i];
  }

  ll _q;
  cin >> _q;
  std::vector<int> _l(_q), _r(_q), _v(_q);
  for(ll i = 0; i < _q; i ++) {
    cin >> _l[i] >> _r[i] >> _v[i];
  }

  std::vector<int> _ans = distribute_candies(_c, _l, _r, _v);

  for(auto j : _ans) cout << j << " ";
}
#endif // lpv

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

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:71:24: warning: narrowing conversion of 'query(1, 1, q, a[i])' from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} [-Wnarrowing]
   71 |     kq.push_back({query(1, 1, q, a[i])});
      |                   ~~~~~^~~~~~~~~~~~~~~

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