結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:51:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,372 ms / 2,500 ms |
コード長 | 4,751 bytes |
コンパイル時間 | 4,342 ms |
コンパイル使用メモリ | 288,320 KB |
実行使用メモリ | 27,184 KB |
最終ジャッジ日時 | 2025-09-06 13:51:58 |
合計ジャッジ時間 | 35,532 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
/* class segtree: def __init__(self,n): self.size=1 while self.size<n: self.size*=2 self.dat=[0]*(self.size*2) def update(self,x,a): x+=self.size self.dat[x]=a while x>1: x//=2 self.dat[x]=(self.dat[2*x]+self.dat[2*x+1]) def querry(self,u,v): u+=self.size v+=self.size score=0 while u<v: if u&1: score+=self.dat[u] u+=1 if v&1: v-=1 score+=self.dat[v] u//=2 v//=2 return score class segtree2: def __init__(self,n): self.size=1 while self.size<n: self.size*=2 self.dat=[0]*(self.size*2) def update(self,x,a): x+=self.size self.dat[x]+=a while x>1: x//=2 self.dat[x]=(self.dat[2*x]+self.dat[2*x+1]) def querry(self,u,v): u+=self.size v+=self.size score=0 while u<v: if u&1: score+=self.dat[u] u+=1 if v&1: v-=1 score+=self.dat[v] u//=2 v//=2 return score N,M=map(int,input().split()) Zsum=segtree(M+2) Zcount=segtree2(M+2) L=[] p=[0]*N h=[[0]*2 for i in range(N)] T=[0]*N for i in range(N): a,l,r=map(int,input().split()) Zsum.update(i+1,a) Zcount.update(l,1) Zcount.update(r+1,-1) L.append((a,l,r)) p[i]=a h[i][0]=l h[i][1]=r T[i]=i+1 score=0 for i in range(N): a,l,r=L[i][:] score+=a*(r-l+1)-Zsum.querry(l,r+1) Q=int(input()) for _ in range(Q): pos,y,c,d=map(int,input().split()) pos-=1 now=T[pos] a=p[pos] l,r=h[pos][:] h[pos][0]=c h[pos][1]=d score-=a*(r-l+1)-Zsum.querry(l,r+1) Zcount.update(l,-1) Zcount.update(r+1,1) count=Zcount.querry(0,now+1) score+=count*a Zsum.update(now,0) Zsum.update(y,a) score+=a*(d-c+1)-Zsum.querry(c,d+1) count=Zcount.querry(0,y+1) score-=count*a Zcount.update(c,1) Zcount.update(d+1,-1) T[pos]=y print(score) */ #include <bits/stdc++.h> using namespace std; class segtree { public: int size; vector<long long> dat; segtree(int n) { size = 1; while (size < n) size *= 2; dat.assign(2 * size, 0); } void update(int x, long long a) { x += size; dat[x] = a; while (x > 1) { x /= 2; dat[x] = dat[2 * x] + dat[2 * x + 1]; } } long long querry(int u, int v) { u += size; v += size; long long score = 0; while (u < v) { if (u & 1) score += dat[u++]; if (v & 1) score += dat[--v]; u /= 2; v /= 2; } return score; } }; class segtree2 { public: int size; vector<long long> dat; segtree2(int n) { size = 1; while (size < n) size *= 2; dat.assign(2 * size, 0); } void update(int x, long long a) { x += size; dat[x] += a; while (x > 1) { x /= 2; dat[x] = dat[2 * x] + dat[2 * x + 1]; } } long long querry(int u, int v) { u += size; v += size; long long score = 0; while (u < v) { if (u & 1) score += dat[u++]; if (v & 1) score += dat[--v]; u /= 2; v /= 2; } return score; } }; int main() { int N, M; cin >> N >> M; segtree Zsum(M + 2); segtree2 Zcount(M + 2); vector<tuple<int, int, int>> L; vector<int> p(N); vector<vector<int>> h(N, vector<int>(2)); vector<int> T(N); for (int i = 0; i < N; ++i) { int a, l, r; cin >> a >> l >> r; Zsum.update(i + 1, a); Zcount.update(l, 1); Zcount.update(r + 1, -1); L.emplace_back(a, l, r); p[i] = a; h[i][0] = l; h[i][1] = r; T[i] = i + 1; } long long score = 0; for (int i = 0; i < N; ++i) { int a, l, r; tie(a, l, r) = L[i]; score += 1LL * a * (r - l + 1) - Zsum.querry(l, r + 1); } int Q; cin >> Q; while (Q--) { int pos, y, c, d; cin >> pos >> y >> c >> d; pos -= 1; int now = T[pos]; int a = p[pos]; int l = h[pos][0]; int r = h[pos][1]; h[pos][0] = c; h[pos][1] = d; score -= 1LL * a * (r - l + 1) - Zsum.querry(l, r + 1); Zcount.update(l, -1); Zcount.update(r + 1, 1); long long count = Zcount.querry(0, now + 1); score += count * a; Zsum.update(now, 0); Zsum.update(y, a); score += 1LL * a * (d - c + 1) - Zsum.querry(c, d + 1); count = Zcount.querry(0, y + 1); score -= count * a; Zcount.update(c, 1); Zcount.update(d + 1, -1); T[pos] = y; cout << score << '\n'; } return 0; }