結果
| 問題 | No.3464 Max and Sum on Grid |
| コンテスト | |
| ユーザー |
 syndrome
|
| 提出日時 | 2026-02-28 20:58:10 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,840 bytes |
| 記録 | |
| コンパイル時間 | 5,783 ms |
| コンパイル使用メモリ | 381,972 KB |
| 実行使用メモリ | 11,648 KB |
| 最終ジャッジ日時 | 2026-02-28 20:58:24 |
| 合計ジャッジ時間 | 12,449 ms |
|
ジャッジサーバーID （参考情報） |
judge7 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | TLE * 1 -- * 9 |
ソースコード
// (◕ᴗ◕✿)
// #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){
assert (0 <= p && p < _n);
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){
assert(0 <= p && p < _n);
return tree[p + size];
}
T prod(int l, int r){
assert (0 <= l && l <= r && r <= _n);
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();
}