結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:07:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 462 ms / 2,500 ms |
コード長 | 2,152 bytes |
コンパイル時間 | 3,796 ms |
コンパイル使用メモリ | 286,548 KB |
実行使用メモリ | 15,744 KB |
最終ジャッジ日時 | 2025-09-06 14:08:04 |
合計ジャッジ時間 | 17,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;} constexpr ll INFLL = (1LL << 62), MOD = 998244353; constexpr int INF = (1 << 30); template <typename T> struct BIT{ int n; vector<T> data[2]; BIT(int _n=0) : n(_n){ init(); } void init(){ rep(i,2) data[i].assign(n+1, 0); } T sum_sub(int p, int i){ T res = 0; for(; i; i -= i&-i) res += data[p][i]; return res; } T sum(int i){ return sum_sub(0,i) + sum_sub(1,i)*i; } void add_sub(int p, int i, T x){ for(; i <= n; i += i&-i) data[p][i] += x; } //[l,r) void add(int l, int r, T x){ add_sub(0, l, -x*(l-1)); add_sub(0, r, x*(r-1)); add_sub(1, l, x); add_sub(1, r, -x); } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin >> n >> m; ll ans = 0; BIT<ll> bit1(m), bit2(m); vector<ll> a(n), l(n), r(n), idx(n); rep(i,n){ idx[i] = i; cin >> a[i] >> l[i] >> r[i]; --l[i]; ans += a[i]*(r[i]-l[i]); bit1.add(idx[i]+1,idx[i]+2,a[i]); bit2.add(l[i]+1,r[i]+1,1); } rep(i,n) ans -= (bit2.sum(idx[i]+1) - bit2.sum(idx[i])) * a[i]; int q; cin >> q; while(q--){ int x,y,u,v; cin >> x >> y >> u >> v; --x; --y, --u; ans -= a[x]*(r[x]-l[x]); ans += (bit2.sum(idx[x]+1) - bit2.sum(idx[x])) * a[x]; bit1.add(idx[x]+1,idx[x]+2,-a[x]); ans += bit1.sum(r[x]) - bit1.sum(l[x]); bit2.add(l[x]+1,r[x]+1,-1); l[x] = u, r[x] = v, idx[x] = y; bit1.add(idx[x]+1,idx[x]+2,a[x]); ans -= (bit2.sum(idx[x]+1) - bit2.sum(idx[x])) * a[x]; bit2.add(l[x]+1,r[x]+1,1); ans += a[x]*(r[x]-l[x]); ans -= bit1.sum(r[x]) - bit1.sum(l[x]); cout << ans << '\n'; } return 0; }