Submission #25033933

---

Source Code Expand

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll, null_type, less_equal<>, rb_tree_tag,
//    tree_order_statistics_node_update> ordered_set;

ld eps = (ld) 1 / 1e6;
ll inf_ll = 1e18 + 100, mod1 = 1e9 + 7, mod2 = 998244353;
ll mersen_mod = 2305843009213693951;

ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll add(ll a, ll b, ll mod) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
ll sub(ll a, ll b, ll mod) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
ll binpow(ll a, ll b, ll mod) {
  return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod :
              sqr(binpow(a, b / 2, mod)) % mod) : 1;
}
ll binmult(ll a, ll b, ll mod) {
  return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod :
              (2 * binmult(a, b / 2, mod)) % mod) : 0;
}

/// Code here
pll a[200001];
ll ans[200001];
bool used[200001];
multiset<pll> mst;

int main() {
  fast_io;
  ll n, i;
  cin >> n;
  for (i = 1; i <= n; i++) cin >> a[i].first;
  for (i = 1; i <= n; i++) cin >> a[i].second, ans[i] = a[i].second, mst.insert({a[i].second, i});
  while (!mst.empty()) {
    auto f = mst.begin();
    ll cs = a[f->second].first, ct = f->first, cid = f->second;
    mst.erase(f);
    if (used[cid]) continue;
    used[cid] = 1;
    ans[cid] = ct;
    ll nxt = cid + 1;
    if (nxt > n) nxt = 1;
    if (ct + cs < ans[nxt] && !used[nxt]) mst.insert({ct + cs, nxt});
  }
  for (i = 1; i <= n; i++) cout << ans[i] << '\n';
  //cerr << '\n' << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << '\n';
  return 0;
}

Submission Info

Judge Result