結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:28:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 925 ms / 2,500 ms |
コード長 | 5,373 bytes |
コンパイル時間 | 4,540 ms |
コンパイル使用メモリ | 259,940 KB |
実行使用メモリ | 33,304 KB |
最終ジャッジ日時 | 2025-09-06 14:28:40 |
合計ジャッジ時間 | 27,926 ms |
ジャッジサーバーID (参考情報) |
judge / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
// https://qiita.com/Raclamusi/items/660f0f42c57e4371ed78 #ifdef INCLUDED_MAIN // 区間加算・区間最小値取得 // 値の乗せ方:https://betrue12.hateblo.jp/entry/2020/09/22/194541 // チートシート:https://betrue12.hateblo.jp/entry/2020/09/23/005940 using S2 = ll; const S2 E2 = 0; S2 op2(S2 a, S2 b) { return a + b; } S2 e2() { return E2; } using Seg = atcoder::segtree<S2, op2, e2>; // S target = 0; // target以上の最小の値を持つ区間の左端を返す // ref:https://qiita.com/recuraki/items/ae8e965b84f0e5443dc5 // bool min_left(S x){ // return x < target; // } // 区間加算・区間最小値取得 // 値の乗せ方:https://betrue12.hateblo.jp/entry/2020/09/22/194541 // チートシート:https://betrue12.hateblo.jp/entry/2020/09/23/005940 struct S { long long value; int size; }; using F = long long; S op(S a, S b) { return {a.value + b.value, a.size + b.size}; } S e() { return {0, 0}; } S mapping(F f, S x) { return {x.value + f * x.size, x.size}; } F composition(F f, F g) { return f + g; } F id() { return 0; } using lazy_seg = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; // S target = 0; // target以上の最小の値を持つ区間の左端を返す // ref:https://qiita.com/recuraki/items/ae8e965b84f0e5443dc5 // bool min_left(S x){ // return x < target; // } auto solve(int N, ll M, std::vector<ll> &A, std::vector<ll> &L, std::vector<ll> &R, int Q, std::vector<ll> &X, std::vector<ll> &Y, std::vector<ll> &U, std::vector<ll> &V) { // TODO: edit here vc<ll> house(N); iota(all(house), 0); Seg seg(M); rep(i, N) { seg.set(i, A[i]); } std::vector<S> v(M, {0, 1}); lazy_seg lseg(v); ll sum = 0; rep(i, N) { sum += A[i] * (R[i] - L[i] + 1) - seg.prod(L[i] - 1, R[i]); lseg.apply(L[i] - 1, R[i], 1); } rep(i, Q) { // rep(j, M) // { // cout << lseg.get(j).value << ' '; // } // cout << '\n'; // rep(j, M) // { // cout << seg.get(j) << ' '; // } lseg.apply(L[X[i] - 1] - 1, R[X[i] - 1], -1); sum += lseg.get(house[X[i] - 1]).value * (A[X[i] - 1]); sum -= A[X[i] - 1] * (R[X[i] - 1] - L[X[i] - 1] + 1) - seg.prod(L[X[i] - 1] - 1, R[X[i] - 1]); seg.set(house[X[i] - 1], 0); seg.set(Y[i] - 1, A[X[i] - 1]); L[X[i] - 1] = U[i]; R[X[i] - 1] = V[i]; house[X[i] - 1] = Y[i] - 1; sum -= lseg.get(house[X[i] - 1]).value * (A[X[i] - 1]); sum += A[X[i] - 1] * (R[X[i] - 1] - L[X[i] - 1] + 1) - seg.prod(L[X[i] - 1] - 1, R[X[i] - 1]); cout << sum << '\n'; lseg.apply(L[X[i] - 1] - 1, R[X[i] - 1], 1); } } // generated by oj-template v4.8.1 (https://github.com/online-judge-tools/template-generator) int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); // ref:https://rsk0315.hatenablog.com/entry/2020/05/09/170315 // ll T; // cin >> T; // rep(i, T)solve(); int N; ll M; int Q; std::cin >> N; std::vector<ll> A(N), L(N), R(N); std::cin >> M; rep(i, N) { std::cin >> A[i] >> L[i] >> R[i]; } std::cin >> Q; std::vector<ll> X(Q), Y(Q), U(Q), V(Q); rep(i, Q) { std::cin >> X[i] >> Y[i] >> U[i] >> V[i]; } solve(N, M, A, L, R, Q, X, Y, U, V); return 0; } #else // #ifndef ONLINE_JUDGE // #define _GLIBCXX_DEBUG 1 //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意 // #endif #ifdef ONLINE_JUDGE #define NDEBUG #include <atcoder/all> #endif #include <bits/stdc++.h> // # include <boost/multiprecision/cpp_dec_float.hpp> // # include <boost/multiprecision/cpp_int.hpp> // # include <boost/rational.hpp> // namespace mp = boost::multiprecision; // // 任意長整数型 // using Bint = mp::cpp_int; // // 仮数部が32桁(10進数)の浮動小数点数型 // using Real32 = mp::number<mp::cpp_dec_float<32>>; // // 仮数部が1024桁(10進数)の浮動小数点数型 // using Real1024 = mp::number<mp::cpp_dec_float<1024>>; // // ついでに有理数型 // using Rat = boost::rational<Bint>; using namespace atcoder; using namespace std; using ll = long long; using ld = long double; #define double ld ll INF = 2e18; using P = pair<ll, ll>; #define pb push_back #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define reprev(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--) #define reps(i, n) for (ll i = 1; i <= (ll)(n); i++) #define for_(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) #define all(v) v.begin(), v.end() template <typename T> inline bool chmin(T &a, const T &b) { bool c = a > b; if (c) a = b; return c; } template <typename T> inline bool chmax(T &a, const T &b) { bool c = a < b; if (c) a = b; return c; } template <typename T> inline T ceil(T a, T b) { return (a + (b - 1)) / b; } using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<10>;//使うときはコメントアウトを外す template <typename T> using vc = vector<T>; template <class T> istream &operator>>(istream &i, vc<T> &v) { rep(j, (ll)size(v)) i >> v[j]; return i; } template <class T> ostream &operator<<(ostream &o, const vc<T> &v) { rep(j, (ll)size(v)) { if (j) o << " "; o << v[j]; } o << endl; return o; } #define INCLUDED_MAIN #include __FILE__ #endif