#1150673 (C++17) No.3464 Max and Sum on Grid

• 問題: No.3464 Max and Sum on Grid
• ユーザー: 0214sh7
• 提出日時: 2026-02-28 16:23:16
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,795 bytes
• コンパイル時間: 1,873 ms
• コンパイル使用メモリ: 134,240 KB
• 実行使用メモリ: 51,072 KB
• 最終ジャッジ日時: 2026-02-28 16:23:30
• 合計ジャッジ時間: 14,212 ms
• ジャッジサーバーID （参考情報）: judge7 / judge2

ファイルパターン	結果
sample	WA * 1
other	WA * 7 RE * 3

ソースコード

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <bitset>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> PP;
// #define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951ll
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define ORREP(i,n) for(ll i=(n);i>=1;--i)
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define chmin(k,m) k = min(k,m)
#define chmax(k,m) k = max(k,m)
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

template<typename T>
class segmenttree{
    // Copyright (c) 2024 0214sh7
    // https://github.com/0214sh7/library/
    private:
    int n;
    int size_;
    std::vector<T> dat;
    std::function<T(T,T)> calc;
    T id;

    public:

    void init(int N, std::function<T(T,T)> func, T e){
        size_ = N;
        n = 1;
        while(n<N)n<<=1;
        calc = func;
        id = e;
        dat.assign(2*n-1,e);
    }

    void init(std::vector<T> a, std::function<T(T,T)> func, T e){
        init(a.size(),func,e);
        set(a);
    }

    segmenttree(int N, std::function<T(T,T)> func, T e){
        init(N,func,e);
    }

    segmenttree(std::vector<T> a, std::function<T(T,T)> func, T e){
        init(a,func,e);
    }

    void set(int k, T a){
        assert(0<=k && k<size_);
        k += n-1;
        dat[k] = a;
        while(k>0){
            k = (k-1)/2;
            dat[k] = calc(dat[2*k+1],dat[2*k+2]);
        }
    }

    void set(std::vector<T> a){
        assert((int)a.size()==size_);
        dat.assign(2*n-1,id);
        for(int k=0;k<size_;k++){
            dat[n+k-1] = a[k];
        }
        for(int k=n-2;k>=0;k--){
            dat[k] = calc(dat[2*k+1],dat[2*k+2]);
        }
    }

    T prod(int a,int b){
        assert(0<=a && a<=b && b<=size_);
        a += n-1;
        b += n-1;
        T L = id, R = id;
        while(a<b){
            if(a%2==0){
                L = calc(L,dat[a]);
                a++;
            }
            a = (a-1)/2;
            if(b%2==0){
                b--;
                R = calc(dat[b],R);
            }
            b = (b-1)/2;
        }
        return calc(L,R);
    }

    int max_right(int l, std::function<bool(T)> f){
        assert(0<=l && l<=size_);
        assert(f(id));

        l += n-1;
        int k = l;
        int sum = id;
        
        while(1){
            while(k%2==1)k=(k-1)/2;
            T newsum = calc(sum,dat[k]);
            if(f(newsum)){
                sum = newsum;
                if(((k+2) & -(k+2)) == (k+2)){
                    return size_;
                }
                k++;
            }else{
                break;
            }
        }

        while(k < n-1){
            T newsum = calc(sum,dat[2*k+1]);
            if(f(newsum)){
                sum = newsum;
                k = 2*k+2;
            }else{
                k = 2*k+1;
            }
        }

        return k-n+1;
    }
    
    int min_left(int r, std::function<bool(T)> f){
        assert(0<=r && r<=size_);
        assert(f(id));
        if(r==0)return 0;

        r += n-1;r--;
        int k = r;
        int sum = id;
        
        while(1){
            while(k%2==0)k=(k-1)/2;
            T newsum = calc(dat[k],sum);
            if(f(newsum)){
                sum = newsum;
                if(((k+1) & -(k+1)) == (k+1)){
                    return 0;
                }
                k--;
            }else{
                break;
            }
        }

        while(k < n-1){
            T newsum = calc(dat[2*k+2],sum);
            if(f(newsum)){
                sum = newsum;
                k = 2*k+1;
            }else{
                k = 2*k+2;
            }
        }

        return k-n+2;
    }

};

int main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll N,Q;
    cin >> N >> Q;
    vector<ll> A(N);
    REP(i,N){cin >> A[i];}
    vector<ll> B(N);
    REP(i,N){cin >> B[i];}

    ll sN = 0;
    while((sN+1)*(sN+1)<=N)sN++;
    N = sN*sN;
    while(A.size()<N){
        A.push_back(0);
        B.push_back(0);
    }

    std::function<long long(long long,long long)> func = [](long long a,long long b){
        return a+b;
    };
    const ll Mx = 100'000;
    segmenttree<long long> SEG(Mx,func,0);
    
    // dp_a[i][j] := A[j*sN] ~ A[(j+1)*sN-1] の間で B[i] 以上のものの和
    vector<vector<ll>> dp_a(N,vector<ll>(sN,0));
    
    // dp_b[i][j] := B[j*sN] ~ B[(j+1)*sN-1] の間で A[i] より大きいものの和
    vector<vector<ll>> dp_b(N,vector<ll>(sN,0));

    REP(j,sN){
        map<ll,ll> mp;
        for(ll k=j*sN;k<(j+1)*sN;k++){
            mp[A[k]]++;
        }
        for(auto p:mp){
            SEG.set(p.first,p.second);
        }
        REP(i,N){
            ll a = SEG.prod(B[i],Mx);
            dp_a[i][j] = a;
        }
        for(auto p:mp){
            SEG.set(p.first,0);
        }
    }

    REP(j,sN){
        map<ll,ll> mp;
        for(ll k=j*sN;k<(j+1)*sN;k++){
            mp[B[k]]++;
        }
        for(auto p:mp){
            SEG.set(p.first,p.second);
        }
        REP(i,N){
            ll b = SEG.prod(A[i]+1,Mx);
            dp_b[i][j] = b;
        }
        for(auto p:mp){
            SEG.set(p.first,0);
        }
    }

    REP(_,Q){

        ll l,d,r,u;
        cin >> l >> d >> r >> u;
        l--;r--;
        d--;u--;
        


    }

    return 0;
    
}