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

• 問題: No.3464 Max and Sum on Grid
• ユーザー: syndrome
• 提出日時: 2026-02-28 20:59:45
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,713 bytes
• コンパイル時間: 5,204 ms
• コンパイル使用メモリ: 385,276 KB
• 実行使用メモリ: 30,552 KB
• 最終ジャッジ日時: 2026-02-28 21:00:49
• 合計ジャッジ時間: 12,673 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

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

ソースコード

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define srep(i, s, n) for (ll i = s; i < (n); i++)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); }

#define debug(var) do { cerr << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cerr << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cerr << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);} cerr << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const multiset<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cerr << " ";} cerr << endl;}

ll op(ll a, ll b){return a + b;}
ll e(){return 0;}
template<class T, T (*op)(T, T), T (*e)()> struct segtree{
    public : 
        segtree(int n) : _n(n){
            depth = 0;
            while ((1 << depth) < _n) depth++;
            size = 1 << depth;
            tree = vc<T>(2 * size, e());
        }

        void set(int p, T x){
            p += size;
            tree[p] = x;
            for (int i = 0; i < depth; i++){
                p >>= 1;
                tree[p] = op(tree[2 * p], tree[2 * p + 1]);
            }
            return;
        }

        T get(int p){
            return tree[p + size];
        }

        T prod(int l, int r){
            if (l == r) return e();
            T nl = e(), nr = e();
            l += size;
            r += size;
            while(l < r){
                if (l & 1) nl = op(nl, tree[l++]);
                // if (r & 1) nr = op(nr, tree[--r]);
                if (r & 1) nr = op(tree[--r], nr);
                l >>= 1;
                r >>= 1;
            }
            return op(nl, nr);
        }
    
    private : 
        int _n, depth, size;
        vc<T> tree;
};

ll hilbertorder(int x, int y, ll maxn) {
  ll rx, ry, d = 0;
  for (ll s = maxn >> 1; s; s >>= 1) {
    rx = (x & s)>0, ry = (y & s)>0;
    d += s * s * ((rx * 3) ^ ry);
    if (ry) continue;
    if (rx) {
      x = maxn - 1 - x;
      y = maxn - 1 - y;
    }
    swap(x, y);
  }
  return d;
}

void mo_algo(int N, vc<pair<int, int>> &querys, auto add_l, auto add_r, auto erase_l, auto erase_r, auto out){
    int Q = len(querys);
    vi order(Q);
    iota(all(order), 0);
    ll maxn = 1;
    while (maxn < N) maxn <<= 1;
    vl eval(Q);
    for (int i = 0; i < Q; i++) eval[i] = hilbertorder(querys[i].first, querys[i].second, maxn);

    sort(all(order), [&](int i, int j) {
        return eval[i] < eval[j];
    });

    int nl = 0, nr = 0;
    for(int i : order) {
        auto& [l, r] = querys[i];
        while(nl > l) add_l(--nl);
        while(nr < r) add_r(nr++);
        while(nl < l) erase_l(nl++);
        while(nr > r) erase_r(--nr);
        out(i);
    }
    return;
}

void solve(){
    int N, Q; cin >> N >> Q;
    int M = 1e5;
    vl A(N); rep(i, N) cin >> A[i];
    vl B(N); rep(i, N) cin >> B[i];
    vc<pair<int, int>> querys;
    while (Q--){
        int l, d, r, u; cin >> l >> d >> r >> u; l--; d--;
        querys.push_back({r, u});
        querys.push_back({r, d});
        querys.push_back({l, u});
        querys.push_back({l, d});
    }
    segtree<ll, op, e> segsmI(M), segcntI(M), segsmJ(M), segcntJ(M);
    ll f = 0;
    vl F(len(querys));
    auto add_l = [&](int i){
        segsmI.set(A[i], segsmI.get(A[i]) + A[i]);
        segcntI.set(A[i], segcntI.get(A[i]) + 1);
        f += segsmJ.prod(A[i], M) + A[i] * segcntJ.prod(0, A[i]);
    };
    auto erase_l = [&](int i){
        segsmI.set(A[i], segsmI.get(A[i]) - A[i]);
        segcntI.set(A[i], segcntI.get(A[i]) - 1);
        f -= segsmJ.prod(A[i], M) + A[i] * segcntJ.prod(0, A[i]);
    };
    auto add_r = [&](int j){
        segsmJ.set(B[j], segsmJ.get(B[j]) + B[j]);
        segcntJ.set(B[j], segcntJ.get(B[j]) + 1);
        f += segsmI.prod(B[j], M) + B[j] * segcntI.prod(0, B[j]);
    };
    auto erase_r = [&](int j){
        segsmJ.set(B[j], segsmJ.get(B[j]) - B[j]);
        segcntJ.set(B[j], segcntJ.get(B[j]) - 1);
        f -= segsmI.prod(B[j], M) + B[j] * segcntI.prod(0, B[j]);
    };
    auto out = [&](int i){
        F[i] = f;
    };
    mo_algo(N, querys, add_l, add_r, erase_l, erase_r, out);
    for (int i = 0; i < len(querys); i += 4){
        cout << -F[i] + F[i + 1] + F[i + 2] - F[i + 3] << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}