結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:25:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,044 ms / 2,500 ms |
コード長 | 1,358 bytes |
コンパイル時間 | 1,016 ms |
コンパイル使用メモリ | 93,804 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2025-09-06 14:26:11 |
合計ジャッジ時間 | 26,945 ms |
ジャッジサーバーID (参考情報) |
judge / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <atcoder/fenwicktree> int main() { int N, M; std::cin >> N >> M; int64_t total_rating = 0, total_diff = 0; atcoder::fenwick_tree<int64_t> count(M + 1), rating(M + 1); std::vector<int> home(N), A(N), L(N), R(N); for (int i = 0; i < N; i++) { std::cin >> A[i] >> L[i] >> R[i]; L[i]--; total_rating += A[i] * int64_t(R[i] - L[i]); home[i] = i; count.add(L[i], 1); count.add(R[i], -1); rating.add(i, A[i]); } for (int i = 0; i < N; i++) { total_diff += A[i] * count.sum(0, home[i] + 1); } int Q; std::cin >> Q; while (Q--) { int X, Y, U, V; std::cin >> X >> Y >> U >> V; X--, Y--, U--; total_rating -= A[X] * int64_t(R[X] - L[X]); total_diff -= A[X] * count.sum(0, home[X] + 1); rating.add(home[X], -A[X]); total_diff -= rating.sum(L[X], R[X]); total_diff += rating.sum(U, V); rating.add(Y, A[X]); count.add(L[X], -1); count.add(R[X], 1); home[X] = Y; L[X] = U; R[X] = V; count.add(U, 1); count.add(V, -1); total_rating += A[X] * int64_t(V - U); total_diff += A[X] * count.sum(0, Y + 1); std::cout << total_rating - total_diff << std::endl; } }