#1150378 (C++23) No.3464 Max and Sum on Grid

• 問題: No.3464 Max and Sum on Grid
• ユーザー: tassei903
• 提出日時: 2026-02-28 15:03:43
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,340 bytes
• コンパイル時間: 4,356 ms
• コンパイル使用メモリ: 355,104 KB
• 実行使用メモリ: 14,196 KB
• 最終ジャッジ日時: 2026-02-28 15:04:08
• 合計ジャッジ時間: 25,080 ms
• ジャッジサーバーID （参考情報）: judge2 / judge7

ファイルパターン	結果
sample	AC * 1
other	WA * 10

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
 
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
 
#define i128 __int128_t
 
struct _ {
   _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    os << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        os << v[i];
        if (i != v.size() - 1) {
            os << ", "; // 最後の要素以外にはカンマとスペースを入れる
        }
    }
    os << "]";
    return os;
}

void debug(auto ...vs) {
    ((cerr << vs << " "), ...) << endl;
}

struct Mo {
   int n;
   vector<pii> lr;
   Mo(int n) : n(n) {}
   void add(int l, int r) { lr.eb(l, r); }
   template<typename AL, typename AR, typename EL, typename ER, typename O>
   void build(const AL& add_left, const AR& add_right, const EL& erase_left, const ER& erase_right, const O& out) {
      int q = (int)lr.size();
      int bs = n / min<int>(n, sqrt(q));
      vector<int> ord(q);
      iota(all(ord), 0);
      sort(all(ord), [&](int a, int b) {
         int ab = lr[a].first / bs, bb = lr[b].first / bs;
         if(ab != bb) return ab < bb;
         return (ab & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second;
      });
      int l = 0, r = 0;
      for(auto idx : ord) {
         while(l > lr[idx].first) add_left(--l);
         while(r < lr[idx].second) add_right(r++);
         while(l < lr[idx].first) erase_left(l++);
         while(r > lr[idx].second) erase_right(--r);
         out(idx);
      }
   }
   template<typename A, typename E, typename O> void build(const A& add, const E& erase, const O& out) {
      build(add, add, erase, erase, out);
   }
};

struct BIT {
   vl a;
   BIT(ll n) : a(n + 1) {}
   void add(ll i, ll x) {
      i++;
      while(i < sz(a)) a[i] += x, i += i & -i;
   }
   ll sum(ll r) {
      ll s = 0;
      while(r) s += a[r], r -= r & -r;
      return s;
   }
   ll sum(ll l, ll r) { return sum(r) - sum(l); }

};

void solve()  {
    int n, q;cin >> n >> q;
    vi a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    const int m = 1e5 + 10;

    BIT bita(m), bitb(m);
    BIT cita(m), citb(m);

    ll score = 0;

    auto adda = [&](int i) -> void {
        score += a[i] * bitb.sum(0, a[i]) + citb.sum(a[i], m);
        bita.add(a[i], 1);
        cita.add(a[i], a[i]);
    };
    auto rema = [&](int i) -> void {
        score -= a[i] * bitb.sum(0, a[i]) + citb.sum(a[i], m);
        bita.add(a[i], -1);
        cita.add(a[i], -a[i]);
    };

    auto addb = [&](int i) -> void {
        score += b[i] * bita.sum(0, b[i]) + cita.sum(b[i], m);
        bitb.add(b[i], 1);
        citb.add(b[i], b[i]);
    };
    auto remb = [&](int i) -> void {
        score -= b[i] * bita.sum(0, b[i]) + cita.sum(b[i], m);
        bitb.add(b[i], -1);
        citb.add(b[i], -b[i]);
    };
    vi res(q * 4);
    auto query = [&](int i) -> void {
        res[i] = score;
    };
    
    Mo mo(n);
    

    // vector<pii> que;
    rep(i, q) {
        int l, d, r, u;cin >> l >> d >> r >> u;
        l -= 1;
        d -= 1;
        mo.add(l, d);
        mo.add(l, u);
        mo.add(r, d);
        mo.add(r, u);
    }
    mo.build(adda, addb, rema, remb, query);
    
    rep(i, q) {
        // debug(res[i*4], res[i*4+1], res[i*4+2], res[i*4+3]);
        cout << -(res[i*4] - res[i*4+1] - res[i*4+2] + res[i*4+3]) << endl;
    }

}   


int main(){
    int T = 1;
    // int T;cin >> T;
    while(T--) {

        solve();
    }
    
}