Submission #67013846

---

Source Code Expand

#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

#define ll long long
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vmi vector<mint>
#define vii vector<pii>
#define rsz resize
#define ep emplace
#define pb pop_back
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define disc(c) (sort(all(c)), (c).rsz(unique(all(c)) - (c).begin()))
#define ers(S, x) ((S).erase((S).find(x)))
#define bit(k) (1u << (k))
#define Bit(k) (1ull << (k))
#define BIT(k) ((UL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 ^ __builtin_clz(x))
#define LG2(x) (63 ^ __builtin_clzll(x))
#define highbit(x) bit(lg2(x))
#define highbitll(x) Bit(LG2(x))
#define popcnt(x) __builtin_popcount(x)
#define popcntll(x) __builtin_popcountll(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define qer(i, r, l) for (int i(r), i##End(l); i > i##End; i = ~-i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

// #define FILERR

#ifdef JYR
#include "debug.h"
#define errm(x, ...) fprintf(stderr, x, ##__VA_ARGS__)
#define errs(x, ...) errm(x "\n", ##__VA_ARGS__)
#else
#define dbg(...) (__VA_ARGS__)
#define dbgArr(...) (__VA_ARGS__)
#define errm(x, ...) (x, ##__VA_ARGS__)
#define errs(x, ...) (x, ##__VA_ARGS__)
#endif

#define __

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }
template<typename T, typename U> T OxO(T _a, U _b) { return _a >= _b ? -1 : _a; }

bool Mbe;

template<class T>
constexpr T power(T a, u64 b, T res = 1) {
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return u64(a) * b % P;
}

template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

constexpr i64 safeMod(i64 x, i64 m) {
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}

constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
    a = safeMod(a, b);
    if (a == 0) {
        return {b, 0};
    }
    
    i64 s = b, t = a;
    i64 m0 = 0, m1 = 1;

    while (t) {
        i64 u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        
        std::swap(s, t);
        std::swap(m0, m1);
    }
    
    if (m0 < 0) {
        m0 += b / s;
    }
    
    return {s, m0};
}

template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
    constexpr ModIntBase() : x(0) {}
    template<std::unsigned_integral T>
    constexpr ModIntBase(T x_) : x(x_ % mod()) {}
    template<std::signed_integral T>
    constexpr ModIntBase(T x_) {
        using S = std::make_signed_t<U>;
        S v = x_ % S(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }
    
    constexpr static U mod() {
        return P;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, mod() - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<mod()>(x, rhs.val());
        return *this;
    }
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() <=> rhs.val();
    }
    
private:
    U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;

struct Barrett {
public:
    Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}

    constexpr u32 mod() const {
        return m;
    }

    constexpr u32 mul(u32 a, u32 b) const {
        u64 z = a;
        z *= b;
        
        u64 x = u64((u128(z) * im) >> 64);
        
        u32 v = u32(z - x * m);
        if (m <= v) {
            v += m;
        }
        return v;
    }

private:
    u32 m;
    u64 im;
};

template<u32 Id>
struct DynModInt {
public:
    constexpr DynModInt() : x(0) {}
    template<std::unsigned_integral T>
    constexpr DynModInt(T x_) : x(x_ % mod()) {}
    template<std::signed_integral T>
    constexpr DynModInt(T x_) {
        int v = x_ % int(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }
    
    constexpr static void setMod(u32 m) {
        bt = m;
    }
    
    static u32 mod() {
        return bt.mod();
    }
    
    constexpr u32 val() const {
        return x;
    }
    
    constexpr DynModInt operator-() const {
        DynModInt res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }
    
    constexpr DynModInt inv() const {
        auto v = invGcd(x, mod());
        assert(v.first == 1);
        return v.second;
    }
    
    constexpr DynModInt &operator*=(const DynModInt &rhs) & {
        x = bt.mul(x, rhs.val());
        return *this;
    }
    constexpr DynModInt &operator+=(const DynModInt &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr DynModInt &operator-=(const DynModInt &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr DynModInt &operator/=(const DynModInt &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
        return lhs.val() <=> rhs.val();
    }
    
private:
    u32 x;
    static Barrett bt;
};

struct FastIO {
    char buf[1 << 20], *p1, *p2;
    char puf[1 << 20], *pf;
    
    FastIO() : p1(buf), p2(buf), pf(puf) {}
    ~FastIO() { fwrite(puf, 1, pf - puf, stdout); }
    
    char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
        return p1 == p2 ? EOF : *p1++;
    }
    
    bool blank(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '	'; }
    
    char rd() {
        char c = gc(); while (blank(c)) c = gc();
        return c;
    }
    
    template<typename T> T rd() {
        T x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        return f ? -x : x;
    }
    
    int rds(char *s) {
        char c = gc(), *S = s;
        while (blank(c)) c = gc();
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }
    
    int rdl(char *s) {
        char c = gc(), *S = s;
        while (c == '\r' || c == '\n') c = gc();
        while (c != '\r' && c != '\n' && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }
    
    void rd(char &c) { c = rd(); }
    
    void rd(char *s) {
        char c = gc();
        while (blank(c)) c = gc();
        if (c == EOF) { *s = 0; return; }
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        *s = 0;
    }
    
    void rd(string &s) {
        char c = gc(); s = "";
        while (blank(c)) c = gc();
        if (c == EOF) return;
        while (!blank(c) && c != EOF) s += c, c = gc();
    }
    
    template<std::unsigned_integral U, U P> void rd(ModIntBase<U, P> &x) { x = rd<U>(); }
    template<u32 Id> void rd(DynModInt<Id> &x) { x = rd<int>(); }
    
    template<typename T> void rd(T &x) {
        x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        if (f) x = -x;
    }
    
    template<typename T, typename... Ts>
    void rd(T& x, Ts&... xs) { rd(x), rd(xs...); }
    
    template<typename T>
    void rda(T* x, int l, int r) { rep(i, l, r) rd(x[i]); }
    
    template<typename T>
    void rda(T* x, int n) { rep(i, 1, n) rd(x[i]); }
    
    void pc(const char &c) {
        if (pf - puf == 1 << 20) fwrite(pf = puf, 1, 1 << 20, stdout);
        *pf++ = c;
    }
    
    void prt(char c) { pc(c); }
    void prt(char* s) { while (*s) pc(*s++); }
    void prt(const char* s) { while (*s) pc(*s++); }
    void prt(bool b) { pc(b ? '1' : '0'); }
    void prt(string s) { for (auto &&c : s) pc(c); }
    
    template<typename T> void prt(T x) {
        static int st[41], tp = 0;
        if (x == 0) { pc('0'); return; }
        if (x < 0) x = -x, pc('-');
        while (x) st[++tp] = x % 10, x /= 10;
        while (tp) pc(st[tp--] + '0');
    }
    
    template<std::unsigned_integral U, U P> void prt(ModIntBase<U, P> &x) { prt(x.val()); }
    template<u32 Id> void prt(DynModInt<Id> x) { prt(x.val()); }
    
    template<typename T> void prt(T *x) { while (*x) pc(*x++); }
    
    template<typename T, typename... Ts>
    void prt(T x, Ts... xs) { prt(x), prt(xs...); }
    
    template<typename T> void prb(T x) { prt(x, ' '); }
    
    template<typename T> void prt(vector<T> vt) { for (auto x : vt) prb(x); }
    
    template<typename T, typename... Ts>
    void prb(T x, Ts... xs) { prt(x, ' '), prb(xs...); }
    
    template<typename T> void prd(T x) { prt(x, '\n'); }
    
    template<typename T, typename... Ts>
    void prd(T x, Ts... xs) { prt(x, ' '), prd(xs...); }
} IO;

#define rd IO.rd
#define rda IO.rda
#define rds IO.rds
#define rdl IO.rdl
#define r32 rd<int>()
#define r64 rd<i64>()
#define prt IO.prt
#define prs(...) prt(__VA_ARGS__, '\n')
#define prb IO.prb
#define prd IO.prd
#define edl IO.pc('\n')

#define MC

#define N 300005
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

template<u32 Id>
Barrett DynModInt<Id>::bt = mod;

using Z = ModInt<mod>;

int n, m;
vi a, b;

void mslv() {
    rd(n, m), a.rsz(n), b.rsz(n);
    req(i, 0, n) rd(a[i]);
    req(i, 0, n) rd(b[i]);
    req(i, 0, n) a[i] = (m - a[i]) % m;
    sort(all(a)), sort(all(b));
    req(i, 0, n) b.eb(b[i] + m);
    int l = -1, r = n;
    while (r - l > 1) {
        int t = (l + r) >> 1;
        if ([&]() -> bool {
            req(i, 0, n) if (a[i] > b[i + t]) return 0;
            return 1;
        }()) r = t;
        else l = t;
    }
    int ans = 0;
    req(i, 0, n) chkmx(ans, b[i + r] - a[i]);
    prs(ans);
}

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    errs("\033[1;34mRunning!\033[0;m");
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #ifdef FILERR
    freopen("Test.err", "w", stderr);
    #endif
    #endif
    mprw();
    #ifdef MC
    int _ = r32;
    while (_--) errs("------------------------------"), mslv();
    errs("------------------------------");
    #else
    mslv();
    #endif
    #ifdef JYR
    errm("%.3lfMB ", abs(&Med - &Mbe) / 1048576.);
    errm("%.0lfms\n", clock() * 1000. / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Submission Info

Compile Error

./Main.cpp:526:22: warning: left operand of comma operator has no effect [-Wunused-value]
    while (_--) errs("------------------------------"), mslv();
                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:55:23: note: expanded from macro 'errs'
#define errs(x, ...) (x, ##__VA_ARGS__)
                      ^
./Main.cpp:527:10: warning: expression result unused [-Wunused-value]
    errs("------------------------------");
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:55:23: note: expanded from macro 'errs'
#define errs(x, ...) (x, ##__VA_ARGS__)
                      ^
2 warnings generated.

Judge Result