結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:58:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,053 ms / 2,500 ms |
コード長 | 1,228 bytes |
コンパイル時間 | 3,630 ms |
コンパイル使用メモリ | 284,288 KB |
実行使用メモリ | 10,240 KB |
最終ジャッジ日時 | 2025-09-06 14:59:30 |
合計ジャッジ時間 | 28,124 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <cstdlib> #include <math.h> #include <atcoder/fenwicktree> using namespace std; using ll = long long; int main(){ int n,m; cin >> n >> m; vector<ll>a(m); vector<int>p(n); vector<int>l(n); vector<int>r(n); atcoder::fenwick_tree<ll> as(m+1),c(m+1); ll ansp=0,ansm=0; for(int i=0;i<n;i++){ cin >> a[i] >> l[i] >> r[i]; p[i]=i; l[i]--; c.add(l[i],1); c.add(r[i],-1); as.add(i,a[i]); ansp+=a[i]*(r[i]-l[i]); } for(int i=0;i<n;i++){ ansm+=a[i]*c.sum(0,i+1); } int q; cin >> q; while(q--){ int x,y,u,v; cin >> x >> y >> u >> v; x--;y--; u--; ansp-=a[p[x]]*(r[x]-l[x]); ansm-=as.sum(l[x],r[x]); c.add(l[x],-1); c.add(r[x],1); ansm-=a[p[x]]*c.sum(0,p[x]+1); r[x]=v; l[x]=u; a[y]=a[p[x]]; as.add(y,a[p[x]]); as.add(p[x],-a[p[x]]); a[p[x]]=0; p[x]=y; ansp+=a[y]*(v-u); ansm+=a[y]*c.sum(0,y+1); c.add(u,1); c.add(v,-1); ansm+=as.sum(l[x],r[x]); cout << ansp-ansm << endl; } return 0; }