結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー ゼリトキ
提出日時 2025-09-06 15:03:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 298 ms / 2,500 ms
コード長 1,789 bytes
コンパイル時間 3,435 ms
コンパイル使用メモリ 276,140 KB
実行使用メモリ 12,096 KB
最終ジャッジ日時 2025-09-06 15:04:00
合計ジャッジ時間 14,213 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ll long long
const long long mod=998244353;
const long long hmod=46216567629137;
int N,M;
ll bit1[200009],bit2[200009];//1がレート,2が人数
ll sum1(int i){
    ll s=0;
    while(i>=1){
        s+=bit1[i];
        i-=i&-i;
    }
    return s;
}
void add1(int i,ll x){
    while(i<=M){
        bit1[i]+=x;
        i+=i&-i;
    }
}
ll sum2(int i){
    ll s=0;
    while(i>=1){
        s+=bit2[i];
        i-=i&-i;
    }
    return s;
}
void add2(int i,ll x){
    while(i<=M){
        bit2[i]+=x;
        i+=i&-i;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>N>>M;
    ll A[N+1],L[N+1],R[N+1];
    for(int i=1;i<=N;i++) cin>>A[i]>>L[i]>>R[i];
    int pos[N+1];
    for(int i=1;i<=N;i++) pos[i]=i;
    for(int i=1;i<=M;i++){
        bit1[i]=0;
        bit2[i]=0;
    }
    for(int i=1;i<=N;i++){
        add1(i,A[i]);
        add2(L[i],1);
        add2(R[i]+1,-1);
    }
    ll ans=0;
    for(int i=1;i<=N;i++){
        ans+=A[i]*(R[i]-L[i]+1);
        ans-=sum1(R[i])-sum1(L[i]-1);
    }
    int Q;
    cin>>Q;
    for(int z=1;z<=Q;z++){
        ll X,Y,U,V;
        cin>>X>>Y>>U>>V;
        ans-=A[X]*(R[X]-L[X]+1);
        ans+=sum1(R[X])-sum1(L[X]-1);
        ans+=A[X]*(sum2(pos[X]));
        if(L[X]<=pos[X] && pos[X]<=R[X]) ans-=A[X];
        //もと居たところの削除
        add1(pos[X],-A[X]);
        add2(R[X]+1,1);
        add2(L[X],-1);
        L[X]=U;
        R[X]=V;
        pos[X]=Y;
        //追加
        add1(Y,A[X]);
        add2(U,1);
        add2(V+1,-1);

        ans+=A[X]*(V-U+1);
        ans-=sum1(V)-sum1(U-1);
        ans-=sum2(Y)*A[X];
        if(U<=Y && Y<=V) ans+=A[X];
        cout<<ans<<"\n";
    }

}
0