結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 13:58:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,710 ms / 2,500 ms |
コード長 | 1,043 bytes |
コンパイル時間 | 3,833 ms |
コンパイル使用メモリ | 282,760 KB |
実行使用メモリ | 21,024 KB |
最終ジャッジ日時 | 2025-09-06 13:59:23 |
合計ジャッジ時間 | 42,585 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; #include <atcoder/lazysegtree> using atcoder::lazy_segtree; ll op(ll x,ll y){ return x+y; } ll e(){ return 0; } int main(){ int n,m; cin>>n>>m; vector<ll> a(n); vector<int> l(n),r(n); for(int i=0;i<n;i++){ cin>>a[i]>>l[i]>>r[i]; l[i]--; } int q; cin>>q; vector<int> vv(n,-1); for(int i=0;i<n;i++)vv[i]=i; ll ans=0; lazy_segtree<ll,op,e,ll,op,op,e> st(m),st2(m); for(int i=0;i<n;i++)st.set(i,a[i]); for(int i=0;i<n;i++){ ans+=a[i]*(r[i]-l[i]); //cout<<l[i]<<" "<<r[i]<<endl; ans-=st.prod(l[i],r[i]); st2.apply(l[i],r[i],1); } while(q--){ int x,y,u,v; cin>>x>>y>>u>>v; x--;y--;u--; ans-=a[x]*(r[x]-l[x]); //cout<<l[x]<<" "<<r[x]<<endl; ans+=st.prod(l[x],r[x]); st.set(vv[x],0); st2.apply(l[x],r[x],-1); ans+=a[x]*st2.get(vv[x]); // cout<<ans<<endl; ans-=a[x]*st2.get(y); vv[x]=y; st.set(y,a[x]); ans+=a[x]*(v-u); //cout<<u<<" "<<v<<endl; ans-=st.prod(u,v); st2.apply(u,v,1); cout<<ans<<endl; l[x]=u;r[x]=v; } }