結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:25:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 883 ms / 2,500 ms |
コード長 | 10,397 bytes |
コンパイル時間 | 1,893 ms |
コンパイル使用メモリ | 175,984 KB |
実行使用メモリ | 19,724 KB |
最終ジャッジ日時 | 2025-09-06 14:25:40 |
合計ジャッジ時間 | 22,180 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#define MOD_IS_998 1 #if ! defined(ONLINE_JUDGE) && __has_include("template.hpp") #include "template.hpp" #else // template start #include <algorithm> #include <cassert> #include <concepts> #include <cstdint> #include <functional> #include <ios> #include <iostream> #include <istream> #include <limits> #include <map> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <stdexcept> #include <string> #include <type_traits> #include <unordered_map> #include <utility> #include <vector> #include <version> #include <atcoder/modint.hpp> using namespace std; using ll = long long; using pall = pair<ll, ll>; template<class T> using vec = vector<T>; template<class T> using veve = vec<vec<T>>; using vell = vec<ll>; using vest = vec<string>; using vebo = basic_string<bool>; using vevell = veve<ll>; template<class T> using mset = multiset<T>; template<class T> using priority_queue_ascend = priority_queue<T, vec<T>, greater<T>>; constexpr ll inf = numeric_limits<ll>::max(); const string sp = " "; const string lf = "\n"; inline const auto &npos = string::npos; const vec<pall> grid_move4 = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; const vec<pall> grid_move8 = [] { auto ret = grid_move4; ret.insert(ret.end(), {{-1, 1}, {-1, -1}, {1, -1}, {1, 1}}); return ret; }(); #define cont continue #define br break #define whlie while #define foR for #define reutnr return #define retunr return #define reutrn return #define auot auto #define uato auto #define cosnt const #define conts const #define ocnst const inline auto &ciN = cin; inline auto &icn = cin; inline auto &icN = cin; constexpr bool ture = true; constexpr bool flase = false; namespace rnages = ranges; namespace ra = ranges; using namespace atcoder; #define times(N) \ static_assert(is_integral_v<decltype(N)>, "times(): N must be integral"); \ assert((N) >= 0); \ for(typedef remove_cvref_t<decltype(N)> _int; \ [[maybe_unused]] const _int ii : views::iota((_int)0, (N))) #define tiems times #define itmes times template<int M> istream &operator>>(istream &in, static_modint<M> &i) { ll tmp; in >> tmp; i = tmp; return in; } template<int M> ostream &operator<<(ostream &out, const static_modint<M> &i) { return out << i.val(); } template<class T, class U> istream &operator>>(istream &in, pair<T, U> &p) { return in >> p.first >> p.second; } template<class T, class U> ostream &operator<<(ostream &out, const pair<T, U> &p) { return out << p.first << sp << p.second; } template<class T> istream &operator>>(istream &in, vec<T> &v) { for(auto &&e : v) { in >> e; } return in; } struct debug_stream { template<class T> debug_stream &operator<<([[maybe_unused]] const T &x) { #ifndef ONLINE_JUDGE clog << x; #endif return *this; } debug_stream &operator<<([[maybe_unused]] ostream &(*f)(ostream &)) { #ifndef ONLINE_JUDGE clog << f; #endif return *this; } }; template<class T> concept out_stream = same_as<ostream, T> || same_as<debug_stream, T>; inline debug_stream clog_; #define clog clog_ template<class... Ts> istream &in(Ts &...vecs) { static_assert(sizeof...(vecs) != 0, "myfunc::in(): At least one vector must be provided"); const set sizes = {vecs.size()...}; if(sizes.size() > 1) { throw invalid_argument("myfunc::in(): All vectors must have the same size"); } times(*sizes.begin()) { ((cin >> vecs[ii]), ...); } return cin; } void out(ranges::range auto v, const string delim, out_stream auto &out) { ranges::for_each(v, [&](const auto &e) { out << e << delim; }); } void out(ranges::range auto v, const string delim) { out(v, delim, cout); } inline void yes() noexcept { cout << "Yes" << lf; } inline void no() noexcept { cout << "No" << lf; } inline void yesu() noexcept { cout << "YES" << lf; } inline void nou() noexcept { cout << "NO" << lf; } // [mi, ma) [[nodiscard]] inline uint64_t randint(const uint64_t mi, const uint64_t ma) noexcept { static random_device seed; static mt19937_64 mt(seed()); if(mi > ma) [[unlikely]] return randint(ma, mi); if(mi == ma) [[unlikely]] return mi; const uint64_t w = ma - mi; uint64_t r; do { r = mt(); } while(mt.max() - mt.max() % w <= r); return r % w + mi; } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto min(T &&a, U &&b) noexcept { return std::min<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto max(T &&a, U &&b) noexcept { return std::max<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class... Args> [[nodiscard]] auto reduce(const ranges::range auto &r, Args &&...args) { return reduce(ranges::cbegin(r), ranges::cend(r), forward<Args>(args)...); } [[nodiscard]] constexpr ll powll(ll a, ll b, const ll m = inf) { if(b < 0) [[unlikely]] throw invalid_argument("powll(): exponent less than zero"); if(m < 1) [[unlikely]] throw invalid_argument("powll(): modulo less than one"); a %= m; ll ret = 1; while(b) { if(b % 2) ret *= a, ret %= m; a *= a, a %= m; b /= 2; } return ret; } template<class T, class U> requires assignable_from<T &, U> && totally_ordered_with<T, U> bool mini(T &var, U &&val) noexcept { const bool cmp = var > val; if(cmp) var = val; return cmp; } template<class T, class U> requires assignable_from<T &, U> && totally_ordered_with<T, U> bool maxi(T &var, U &&val) noexcept { const bool cmp = var < val; if(cmp) var = val; return cmp; } class [[nodiscard]] grid_base { public: grid_base(const ll h, const ll w) noexcept : height(h), width(w) {} [[nodiscard]] ll operator()(const ll i, const ll j) const noexcept { if(! isvalid(i, j)) return -1; return i * width + j; } [[nodiscard]] ll operator()(const pall &p) const noexcept { return (*this)(p.first, p.second); } protected: bool isvalid(const ll i, const ll j) const noexcept { return 0 <= i && 0 <= j && i < height && j < width; } const ll height, width; }; class [[nodiscard]] grid_seen : public grid_base { public: grid_seen(const ll h, const ll w) : grid_base(h, w) { visited = vebo(h * w, false); } [[nodiscard]] bool &seen(const ll i, const ll j) & { if(! isvalid(i, j)) [[unlikely]] throw out_of_range("grid_seen::seen(): out of range"); return visited[i * width + j]; } [[nodiscard]] bool &sen(const ll i, const ll j) & { return seen(i, j); } [[nodiscard]] bool &seen(const pall &p) & { return seen(p.first, p.second); } [[nodiscard]] bool &sen(const pall &p) & { return seen(p); } private: vebo visited; }; using grid_lite = grid_base; template<auto defval, class... Args> requires is_convertible_v<decltype(defval), typename map<Args...>::mapped_type> class default_map : public map<Args...> { using Map = map<Args...>; public: #ifdef __cpp_lib_associative_heterogeneous_insertion template<convertible_to<typename Map::key_type> U> requires requires(Map::key_compare c, Map::key_type t, U u) { c(t, u); c(u, t); } Map::mapped_type &operator[](const U &key) { Map::try_emplace(key, defval); return Map::operator[](key); } template<convertible_to<typename Map::key_type> U> requires requires(Map::key_compare c, Map::key_type t, U u) { c(t, u); c(u, t); } Map::mapped_type &operator[](const U &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #else Map::mapped_type &operator[](const Map::key_type &key) { Map::try_emplace(key, defval); return Map::operator[](key); } Map::mapped_type &operator[](const Map::key_type &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #endif }; template<auto defval, class... Args> requires is_convertible_v<decltype(defval), typename unordered_map<Args...>::mapped_type> class default_unordered_map : public unordered_map<Args...> { using Map = unordered_map<Args...>; public: #ifdef __cpp_lib_associative_heterogeneous_insertion template<class U> requires requires(Map::hasher h, U u) { h(u); } Map::mapped_type &operator[](const U &key) { Map::try_emplace(key, defval); return Map::operator[](key); } template<class U> requires requires(Map::hasher h, U u) { h(u); } Map::mapped_type &operator[](const U &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #else Map::mapped_type &operator[](const Map::key_type &key) { Map::try_emplace(key, defval); return Map::operator[](key); } Map::mapped_type &operator[](const Map::key_type &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #endif }; template<class T, class U> requires requires(mset<T>::key_compare c, T t, U u) { c(t, u); } auto erase_single(mset<T> &mset, U &&v) { const auto it = mset.find(v); if(it == mset.end()) [[unlikely]] throw invalid_argument("erase_single(): why v not in mset!?!?"); return mset.erase(it); } void solve(); // template end #endif #ifdef MOD_IS_998 constexpr ll MOD = 998244353; #else constexpr ll MOD = 1e9 + 7; #endif using mint = static_modint<MOD>; int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); ll t = 1; // cin >> t; times(t) solve(); return 0; } #include <atcoder/lazysegtree.hpp> #include <atcoder/segtree.hpp> void solve() { ll n, m; cin >> n >> m; segtree<ll, [](ll a, ll b) { return a + b; }, [] { return 0ll; }> b(m); lazy_segtree<ll, [](ll a, ll b) { return a + b; }, [] { return 0ll; }, ll, [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return a + b; }, [] { return 0ll; }> t(m); ll s = 0; vell a(m); vec<pall> lr(m); vell where(n); iota(where.begin(), where.end(), 0); for(intmax_t i = 0; i < intmax_t(n); i++) { cin >> a[i]; b.set(i, a[i]); ll l, r; cin >> l >> r; l--; t.apply(l, r, 1); lr[i] = {l, r}; } for(intmax_t i=0;i<intmax_t(n);i++) { const auto &[l, r] = lr[i]; s += (r - l) * a[i] - b.prod(l, r); } clog << s << lf; ll q; cin >> q; times(q) { ll x, y, u, v; cin >> x >> y >> u >> v; x--, y--, u--; const auto &[l, r] = lr[x]; s -= (r - l) * a[x] - b.prod(l, r); t.apply(l, r, -1); s -= t.prod(where[x], where[x] + 1) * -a[x]; b.set(where[x], 0); b.set(y, a[x]); where[x] = y; lr[x] = {u, v}; s += (v - u) * a[x] - b.prod(u, v); s += t.prod(y, y + 1) * -a[x]; t.apply(u, v, 1); cout << s << lf; } }