結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー 抹茶フォルマッジ ☕️
提出日時 2025-09-06 15:33:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,951 ms / 2,500 ms
コード長 3,864 bytes
コンパイル時間 4,850 ms
コンパイル使用メモリ 261,192 KB
実行使用メモリ 28,260 KB
最終ジャッジ日時 2025-09-06 15:34:25
合計ジャッジ時間 47,140 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
//using mint = modint1000000007;
using ll = long long;
ll INF = 2e18;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
using vs = vc<string>; using vvs = vv<string>;
using vb = vc<bool>; using vvb = vv<bool>;
using vmint = vc<mint>; using vvmint = vv<mint>;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define drep(i,n) for(ll i=(n)-1; i>=0; i--)
#define rrep(i,n) for(ll i=1; i<=(n); i++)
#define nfor(i,a,b) for(ll i=a;i<b;i++)
#define dfor(i,a,b) for(ll i=(a)-1; i>=(b); i--)
template<class T>istream& operator>>(istream& i, vc<T>& v) {rep(j,(ll) size(v))i >> v[j]; return i; }
#define nall(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {YES;}else{NO;}
#define ERROR cout<<-1<<endl
void print(long double x){ printf("%.20Lf\n",x);}
#define vc_cout(v){ll n = size(v);rep(i,n)cout<<v[i]<<endl;}
#define vv_cout(v){ll n = size(v);rep(i,n){rep(j,size(v[i])){cout<<' '<<v[i][j];}cout<<endl;}}

static const ll INF64  = (1LL<<62);
static const ll NINF64 = -(1LL<<62);

// =============================================================
// 1. 区間加算 + 区間最小
// =============================================================
struct SMin { ll mn; };
using FAdd = ll; // 遅延作用は +f

SMin op_minseg(SMin a, SMin b){ return {min(a.mn, b.mn)}; }
SMin e_minseg(){ return { INF64 }; }
SMin mapping_min(FAdd f, SMin x){ return {x.mn + f}; }
FAdd composition_add(FAdd f, FAdd g){ return f + g; }
FAdd id_add(){ return 0LL; }

using LazyAddMin = lazy_segtree<
    SMin, op_minseg, e_minseg,
    FAdd, mapping_min, composition_add, id_add
>;

struct P_min_ge {
    ll T;
    bool operator()(SMin x) const { return x.mn >= T; }
};



// =============================================================
// 3. 区間加算 + 区間和
// =============================================================
struct SAddSum { ll sum; int sz; };

SAddSum op_addsum(SAddSum a, SAddSum b){ return {a.sum + b.sum, a.sz + b.sz}; }
SAddSum e_addsum(){ return {0LL, 0}; }
SAddSum mapping_addsum(FAdd f, SAddSum x){ return {x.sum + f * x.sz, x.sz}; }

using LazyAddSum = lazy_segtree<
    SAddSum, op_addsum, e_addsum,
    FAdd, mapping_addsum, composition_add, id_add
>;

struct P_sum_le_ll {
    ll K;
    bool operator()(SAddSum x) const { return x.sum <= K; }
};


int main(){
    int N, M;
    cin >> N >> M;
    vc<ll> A(N);
    vi L(N),R(N);
    rep(i,N) {
        cin >> A[i] >> L[i] >> R[i];
        L[i]--;
    }
    vi live(N);
    rep(i,N) live[i] = i;
    vc<SMin> in_range(M,{0});
    LazyAddMin segMin(in_range);
    rep(i,N) {
        segMin.apply(L[i],R[i],1);
    }
    vc<SAddSum> rate(M,{0,1});
    LazyAddSum segSum(rate);
    rep(i,N) {
        segSum.set(i,{A[i],1});
    }
    ll ans = 0;
    rep(i,N) {
        ans -= segSum.prod(L[i],R[i]).sum;
        ans += segSum.prod(L[i],R[i]).sz * A[i];
    }
    int Q;
    cin >> Q;
    rep(q,Q) {
        int x,ny,u,v;
        cin >> x >> ny >> u >> v;
        x--,ny--,u--;
        int y = live[x];
        live[x] = ny;
        ans += A[x] * ((v-u) - (R[x] - L[x]));
        ans += A[x] * segMin.get(y).mn;
        segMin.apply(L[x],R[x],-1);
        segMin.apply(u,v,1);
        ans -= A[x] * segMin.get(ny).mn;
        segSum.set(y,{0,1});
        ans -= segSum.prod(u,v).sum - segSum.prod(L[x],R[x]).sum;
        segSum.set(ny,{A[x],1});
        cout << ans << endl;
        L[x] = u;
        R[x] = v;

    }
}
0