結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:21:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 831 ms / 2,500 ms |
コード長 | 2,964 bytes |
コンパイル時間 | 1,271 ms |
コンパイル使用メモリ | 110,872 KB |
実行使用メモリ | 15,272 KB |
最終ジャッジ日時 | 2025-09-06 14:22:04 |
合計ジャッジ時間 | 22,711 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <iostream> #include <iomanip>//小数点出力用 //cout << fixed << setprecision(10) << ans; #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <unordered_map> using ll = long long; using namespace std; #define modPHash (ll)((1LL<<61)-1) #define modP (ll)998244353 bool chkrng0idx(int pos, int sup) { return (0 <= pos && pos < sup); } int clk4(int num) { return (num - 2) * (num % 2); } void yn(bool tf) { cout << (tf ? "Yes\n" : "No\n"); } #define segL (1<<18) ll segT[segL * 2]; ll segTW[segL * 2]; int c2(int X) { int res = 0; int t = X; if (t == 0)t = segL; while (1) { if (t % 2 == 0) { t /= 2; res++; } else { break; } } return res; } void updateOne(int idx, ll X) { int i = idx + segL; segT[i] = X; i /= 2; while (i >= 1) { segT[i] = segT[2 * i] + segT[2 * i + 1]; i /= 2; } } ll getS(int L, int R) { ll res = 0; int tL = L; while (tL != R) { int b = c2(tL); for (;b >= 0;b--) { if (tL + (1 << b) <= R) { int segIdx = (tL + segL) >> b; res += segT[segIdx]; tL += (1 << b); break; } } } return res; } ll getOne(int idx) {//一点取得 ll res = 0; for (int i = idx + segL;i >= 1;i /= 2) { res += segTW[i]; } return res; } void addR(int L, int R, ll X) { int tL = L; while (tL != R) { int b = c2(tL); for (;b >= 0;b--) { if (tL + (1 << b) <= R) { int segIdx = (tL + segL) >> b; segTW[segIdx] += X; tL += (1 << b); break; } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; int idtopos[200002]; for (int i = 1;i <= N;i++) { idtopos[i] = i; } ll rate[200002]; int L[200002], R[200002]; ll ans = 0; for (int i = 1;i <= N;i++) { cin >> rate[i] >> L[i] >> R[i]; updateOne(i, rate[i]); addR(L[i], R[i] + 1, 1); ans += rate[i] * (ll)(R[i] - L[i] + 1); } for (int i = 1;i <= N;i++) { ans -= getOne(i) * rate[i]; } int Q; cin >> Q; while (Q--) { ll id, go, LL, RR; cin >> id >> go >> LL >> RR; ans += getS(L[id], R[id] + 1); ans -= rate[id] * (ll)(R[id] - L[id] + 1); addR(L[id], R[id] + 1, -1); ans += getOne(idtopos[id]) * rate[id]; updateOne(idtopos[id], 0); L[id] = LL; R[id] = RR; idtopos[id] = go; updateOne(idtopos[id], rate[id]); ans -= getOne(idtopos[id]) * rate[id]; addR(L[id], R[id] + 1, 1); ans += rate[id] * (ll)(R[id] - L[id] + 1); ans -= getS(L[id], R[id] + 1); cout << ans << "\n"; } return 0; }