Submission #44913915

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using ui = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using ull = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(20060130);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + \
  fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
  int x = 0;
  char s = getc();
  while(!isdigit(s)) s = getc();
  while(isdigit(s)) x = x * 10 + s - '0', s = getc();
  return x;
}

#define putc(x) putchar(x)
inline void print(ui x) {
  if(x >= 10) print(x / 10);
  putc(x % 10 + '0');
}

// ---------- templates above ----------

constexpr int N = 2e5 + 5;
constexpr int inf = 2e9 + 7;


int n, m, st;
struct pt {
  int a, b, id;
  bool operator < (const pt &z) {
    return b < z.b;
  }
} p[N];

pii operator + (const pii &x, const int &z) {
  return {x.first + z, x.second};
}
struct dat {
  pii b, ab;
  dat operator + (const dat &z) const {
    return {min(b, z.b), min(ab, z.ab)};
  }
  dat operator + (const int &z) const {
    return {b, min(ab, b + z)};
  }
} val[N << 2];
int laz[N << 2];

void tag(int x, int v) {laz[x] = min(laz[x], v), val[x] = val[x] + v;}
void down(int x) {if(laz[x] < inf) tag(x << 1, laz[x]), tag(x << 1 | 1, laz[x]), laz[x] = inf;}
void build(int l, int r, int x) {
  laz[x] = inf;
  if(l == r) {
    val[x].b = {p[l].b, l};
    val[x].ab = {l == st ? 0 : inf, l};
    return;
  }
  int m = l + r >> 1;
  build(l, m, x << 1);
  build(m + 1, r, x << 1 | 1);
  val[x] = val[x << 1] + val[x << 1 | 1];
}
void modify(int l, int r, int ql, int qr, int x, int v) {
  if(ql <= l && r <= qr) return tag(x, v);
  int m = l + r >> 1;
  down(x);
  if(ql <= m) modify(l, m, ql, qr, x << 1, v);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
  val[x] = val[x << 1] + val[x << 1 | 1];
}
void update(int l, int r, int p, int x) {
  if(l == r) {
    val[x].b = val[x].ab = {inf, p};
    return;
  }
  int m = l + r >> 1;
  down(x);
  if(p <= m) update(l, m, p, x << 1);
  else update(m + 1, r, p, x << 1 | 1);
  val[x] = val[x << 1] + val[x << 1 | 1];
}

void mian() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> p[i].a, p[i].id = i;
  for(int i = 1; i <= n; i++) cin >> p[i].b;
  sort(p + 1, p + n + 1);
  for(int i = 1; i <= n; i++) if(p[i].id == 1) st = i;
  build(1, n, 1);
  for(int i = 1; i <= n; i++) {
    pii res = val[1].ab;
    int id = res.second;
    if(p[id].id == n) cout << res.first << "\n", exit(0);
    int pos = lower_bound(p + 1, p + n + 1, (pt) {0, m - p[id].a}) - p;
    update(1, n, id, 1);
    if(pos <= n) modify(1, n, pos, n, 1, res.first + p[id].a - m);
    if(pos > 1) modify(1, n, 1, pos - 1, 1, res.first + p[id].a);
  }
}


bool Med;
signed main() {
  // fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  while(T--) mian();
  // fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/

Submission Info

Compile Error

./Main.cpp: In function ‘void build(long long int, long long int, long long int)’:
./Main.cpp:85:13: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   85 |   int m = l + r >> 1;
      |           ~~^~~
./Main.cpp: In function ‘void modify(long long int, long long int, long long int, long long int, long long int, long long int)’:
./Main.cpp:92:13: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   92 |   int m = l + r >> 1;
      |           ~~^~~
./Main.cpp: In function ‘void update(long long int, long long int, long long int, long long int)’:
./Main.cpp:103:13: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  103 |   int m = l + r >> 1;
      |           ~~^~~
./Main.cpp: In function ‘void mian()’:
./Main.cpp:121:65: warning: missing initializer for member ‘pt::id’ [-Wmissing-field-initializers]
  121 |     int pos = lower_bound(p + 1, p + n + 1, (pt) {0, m - p[id].a}) - p;
      |                                                                 ^

Judge Result