結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:17:21 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 862 ms / 2,500 ms |
コード長 | 2,471 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 27,264 KB |
実行使用メモリ | 16,000 KB |
最終ジャッジ日時 | 2025-09-06 14:17:44 |
合計ジャッジ時間 | 21,926 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:72:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 72 | scanf("%lld %lld", &n, &m); | ^~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:76:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%lld %lld %lld", &a[i], &l[i], &r[i]); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:98:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 98 | scanf("%lld", &q); | ^~~~~~~~~~~~~~~~~ main.c:101:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 101 | scanf("%lld %lld %lld %lld", &x, &y, &u, &v); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> long long int seg_sum[800005], seg_cnt[800005], ss; void update_sum(long long int x, long long int v) { x += ss - 1; seg_sum[x] = v; while (x > 0) { x = (x - 1) / 2; seg_sum[x] = seg_sum[2 * x + 1] + seg_sum[2 * x + 2]; } return; } long long int get_sum(long long int l, long long int r) { l += ss - 1; r += ss - 1; long long int res = 0; while (l <= r) { if (l % 2 == 0) res += seg_sum[l]; l /= 2; if (r % 2 > 0) res += seg_sum[r]; r = r / 2 - 1; } return res; } void eval(long long int k) { if (k < ss - 1) { seg_cnt[2 * k + 1] += seg_cnt[k]; seg_cnt[2 * k + 2] += seg_cnt[k]; seg_cnt[k] = 0; } return; } void update_cnt(long long int a, long long int b, long long int d, long long int k, long long int l, long long int r) { eval(k); if (a <= l && r <= b) { seg_cnt[k] += d; eval(k); } else if (l < b && a < r) { update_cnt(a, b, d, 2 * k + 1, l, (l + r) / 2); update_cnt(a, b, d, 2 * k + 2, (l + r) / 2, r); } return; } long long int get_cnt(long long int id, long long int k, long long int l, long long int r) { if (l == id && r == id + 1) { return seg_cnt[k]; } eval(k); if (id < (l + r) / 2) return get_cnt(id, 2 * k + 1, l, (l + r) / 2); else return get_cnt(id, 2 * k + 2, (l + r) / 2, r); } long long int a[200005], l[200005], r[200005]; long long int h[200005]; int main() { long long int n, m; scanf("%lld %lld", &n, &m); long long int i, j; for (i = 0; i < n; i++) { scanf("%lld %lld %lld", &a[i], &l[i], &r[i]); l[i]--; r[i]--; h[i] = i; } for (ss = 1; ss < m; ss *= 2); for (i = 0; i < 2 * ss - 1; i++) { seg_sum[i] = 0; seg_cnt[i] = 0; } for (i = 0; i < n; i++) update_sum(i, a[i]); for (i = 0; i < n; i++) update_cnt(l[i], r[i] + 1, 1, 0, 0, ss); long long int ans = 0; for (i = 0; i < n; i++) { ans += (r[i] - l[i] + 1) * a[i]; ans -= get_sum(l[i], r[i]); } long long int q, x, y, u, v; scanf("%lld", &q); for (; q > 0; q--) { scanf("%lld %lld %lld %lld", &x, &y, &u, &v); x--; y--; u--; v--; ans -= (r[x] - l[x] + 1) * a[x]; ans += get_sum(l[x], r[x]); update_sum(h[x], 0); update_cnt(l[x], r[x] + 1, -1, 0, 0, ss); ans += get_cnt(h[x], 0, 0, ss) * a[x]; h[x] = y; l[x] = u; r[x] = v; ans += (r[x] - l[x] + 1) * a[x]; ans -= get_cnt(h[x], 0, 0, ss) * a[x]; update_sum(h[x], a[x]); update_cnt(l[x], r[x] + 1, 1, 0, 0, ss); ans -= get_sum(l[x], r[x]); printf("%lld\n", ans); } return 0; }