結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
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;
}
0