提出 #64228328

---

ソースコード 拡げる

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <limits>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

template <u32 Mod> class ModInt {
    using Self = ModInt<Mod>;
    static_assert(Mod <= std::numeric_limits<i32>::max());
public:
    ModInt(i64 value = 0) {
        if (value < 0) {
            value_ = (Mod - (-value % Mod)) % Mod;
        } else {
            value_ = value % Mod;
        }
    }

    ModInt(const Self& other) : value_(other.value_) {}

    operator i32() const {
        return value_;
    }

    operator i64() const {
        return value_;
    }

    Self operator+(const Self& other) const {
        Self res(*this);
        res += other;
        return res;
    }

    Self operator-(const Self& other) const {
        Self res(*this);
        res -= other;
        return res;
    }

    Self operator*(const Self& other) const {
        Self res(*this);
        res *= other;
        return res;
    }

    Self operator/(const Self& other) const {
        Self res(*this);
        res /= other;
        return res;
    }

    Self operator-() const {
        Self res(0);
        res -= *this;
        return res;
    }

    Self pow(i64 power) const {
        Self ret(1), p(*this);
        if (power < 0) {
            power *= -1;
            p = p.inv();
        }
        for (i64 i = 0; (1 << i) <= power; ++i) {
            if ((power >> i) & 1) ret *= p;
            p *= p;
        }
        return ret;
    }

    Self& operator+=(const Self& other) {
        value_ += other.value_;
        if (value_ >= Mod) value_ -= Mod;
        return *this;
    }

    Self& operator-=(const Self& other) {
        value_ += Mod - other.value_;
        if (value_ >= Mod) value_ -= Mod;
        return *this;
    }

    Self& operator*=(const Self& other) {
        value_ = (u32)(((u64)value_ * other.value_) % Mod);
        return *this;
    }

    Self& operator/=(const Self& other) {
        *this *= other.inv();
        return *this;
    }

    Self inv() const {
        if (value_ < inv_tbl_.size()) return inv_tbl_[value_];
		if (Mod - value_ < inv_tbl_.size()) return Mod - inv_tbl_[Mod - value_];
        else return pow(Mod - 2);
    }

private:
    u32 value_;
    static const std::vector<Self> inv_tbl_;
};

template <u32 Mod>
std::vector<ModInt<Mod>> create_inv_tbl_(u32 n) {
    std::vector<ModInt<Mod>> res;
    res.reserve(n + 1);
    res.push_back(0);
    res.push_back(1);
    for (u32 i = 2; i <= n; ++i) {
        // MOD / i == 0
        // MOD // i + (MOD % i) / i == 0
        // 1 / i == -(MOD // i) / (MOD % i)
        res.push_back(res[Mod % i] * ModInt<Mod>(Mod - (Mod / i)));
    }
    return res;
}

template <u32 Mod>
const std::vector<ModInt<Mod>> ModInt<Mod>::inv_tbl_ = create_inv_tbl_<Mod>(1000000);

template <class T, u32 Mod>
ModInt<Mod> operator+(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) + y;
}

template <class T, u32 Mod>
ModInt<Mod> operator-(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) - y;
}

template <class T, u32 Mod>
ModInt<Mod> operator*(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) * y;
}

template <class T, u32 Mod>
ModInt<Mod> operator/(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) / y;
}

template <class T, u32 Mod>
ModInt<Mod> operator+(ModInt<Mod> x, T y) {
    return x + ModInt<Mod>(y);
}

template <class T, u32 Mod>
ModInt<Mod> operator-(ModInt<Mod> x, T y) {
    return x - ModInt<Mod>(y);
}

template <class T, u32 Mod>
ModInt<Mod> operator*(ModInt<Mod> x, T y) {
    return x * ModInt<Mod>(y);
}

template <class T, u32 Mod>
ModInt<Mod> operator/(ModInt<Mod> x, T y) {
    return x / ModInt<Mod>(y);
}

typedef ModInt<MOD> mint;

int N;
i64 W[202020];
int L[202020], R[202020];
int Q;
i64 ls[404040], rs[404040];

const i64 INFT = 1LL << 60LL;

i64 solve(int s, int t) {
    if (R[s] <= L[t] || R[t] <= L[s]) {
        return 0;
    }

    i64 ret = INFT;
    ret = min(ret, ls[max(R[s], R[t])]);
    ret = min(ret, rs[min(L[s], L[t])]);

    if (R[s] > L[t]) {
        ret = min(ret, ls[R[s]] + rs[L[t]]);
    }
    if (L[s] < R[t]) {
        ret = min(ret, rs[L[s]] + ls[R[t]]);
    }

    return ret;
}

int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%lld", W + i);
    for (int i = 0; i < N; ++i) {
        scanf("%d%d", L + i, R + i);
        --L[i];
    }

    for (int i = 0; i <= 2 * N; ++i) ls[i] = rs[i] = INFT;

    for (int i = 0; i < N; ++i) {
        ls[L[i]] = min(ls[L[i]], W[i]);
        rs[R[i]] = min(rs[R[i]], W[i]);
    }
    for (int i = 2 * N - 1; i >= 0; --i) ls[i] = min(ls[i], ls[i + 1]);
    for (int i = 1; i <= 2 * N; ++i) rs[i] = min(rs[i], rs[i - 1]);

    scanf("%d", &Q);

    for (;Q--;) {
        int s, t;
        scanf("%d%d", &s, &t);
        --s; --t;

        i64 ans = solve(s, t);
        if (ans > INFT / 2) ans = -1;
        else {
            ans += W[s] + W[t];
        }
        printf("%lld\n", ans);
    }
	return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:210:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  210 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:211:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  211 |     for (int i = 0; i < N; ++i) scanf("%lld", W + i);
      |                                 ~~~~~^~~~~~~~~~~~~~~
Main.cpp:213:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  213 |         scanf("%d%d", L + i, R + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:226:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  226 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:230:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  230 |         scanf("%d%d", &s, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~

ジャッジ結果