結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 15:45:56 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,329 ms / 2,500 ms |
コード長 | 11,263 bytes |
コンパイル時間 | 5,647 ms |
コンパイル使用メモリ | 175,076 KB |
実行使用メモリ | 38,184 KB |
最終ジャッジ日時 | 2025-09-06 15:46:55 |
合計ジャッジ時間 | 57,050 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double using LL = long long; using ULL = unsigned long long; using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>; using VL = vector<LL>; using VVL = vector<VL>; using VVVL = vector<VVL>; using VB = vector<bool>; using VVB = vector<VB>; using VVVB = vector<VVB>; using VD = vector<double>; using VVD = vector<VD>; using VVVD = vector<VVD>; using VC = vector<char>; using VS = vector<string>; using VVC = vector<VC>; using PII = pair<int,int>; using PLL = pair<LL,LL>; using PDD = pair<double,double>; using PIL = pair<int,LL>; using MII = map<int,int>; using MLL = map<LL,LL>; using SI = set<int>; using SL = set<LL>; using MSI = multiset<int>; using MSL = multiset<LL>; template<class T> using MAXPQ = priority_queue<T>; template<class T> using MINPQ = priority_queue< T, vector<T>, greater<T> >; const ll MOD = 1000000007; const ll MOD2 = 998244353; const ll INF = 1LL << 60; #define PI 3.14159265358979323846 #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define EACH(e, v) for(auto &e : v) #define RITR(it, v) for(auto it = (v).rbegin(); it != (v).rend(); ++it) #define ALL(v) v.begin(),v.end() vector<ll> x8={1,1,1,0,0,-1,-1,-1},y8={1,0,-1,1,-1,1,0,-1}; int dx4[4]={1,-1,0,0}, dy4[4]={0,0,1,-1}; /* memo -uf,RMQ(segtree),BIT,BIT2,SegTree,SegTreeLazy -isprime,Eratosthenes,gcdlcm,factorize,divisors,modpow,moddiv nCr(+modnCr,inverse,extend_euclid.powmod),tobaseB,tobase10 -dijkstra,Floyd,bellmanford,sccd,topological,treediamiter -compress1,compress2,rotate90 -co,ci,fo1,fo2,fo3,fo4 -bitsearch,binaryserach -bfs -SegTreedec,SegTreeLazydec */ template <typename X, typename M> struct LazySegTree{ using FX = function<X(X,X)>; using FA = function<X(M,X)>; using FM = function<M(M,M)>; long long n, N, log; vector<X> dat; vector<M> lazy; FX fx; FA fa; FM fm; X ex; M em; LazySegTree(long long _n, FX _fx, FA _fa, FM _fm, X _ex, M _em){ init(_n,_fx,_fa,_fm,_ex,_em); } void init(long long _n, FX _fx, FA _fa, FM _fm, X _ex, M _em){ N = _n, fx = _fx, fa = _fa, fm = _fm, ex = _ex, em = _em; long long x = 1; log = 0; while(_n > x) x *= 2, log++; n = x; dat.assign(n*2,ex); lazy.assign(n*2,em); } void pull_dat(long long k){ dat[k] = fx(dat[2*k],dat[2*k+1]); } void apply_lazy(long long k, M f){ dat[k] = fa(f, dat[k]); if(k < n) lazy[k] = fm(f, lazy[k]); } void push_lazy(long long k){ if(lazy[k] == em) return; apply_lazy(2*k, lazy[k]); apply_lazy(2*k + 1, lazy[k]); lazy[k] = em; } void pull_dat_deep(long long k){ for(int h = 1; h <= log; h++) pull_dat(k >> h); } void push_lazy_deep(long long k){ for(int h = log; h >= 1; h--) push_lazy(k >> h); } //i番目の要素をxにアップデートする(0-indexed),O(logN) void set(long long i, X x){ i += n; push_lazy_deep(i); dat[i] = x; pull_dat_deep(i); } //i番目の要素にアクセス(0-indexed),O(logN); X get(long long i){ i += n; push_lazy_deep(i); return dat[i]; } X operator[](long long i){return get(i);}; //i番目の要素にfaを作用させる void apply(long long i, M f){ i += n; push_lazy_deep(i); dat[i] = fa(f, dat[i]); pull_dat_deep(i); } //[l,r)までfaを作用させる void apply(long long l, long long r, M f){ if(l == r) return; l += n, r += n; for(int h = log; h >= 1; h--){ if(((l >> h) << h) != l) push_lazy(l >> h); if(((r >> h) << h) != r) push_lazy((r-1) >> h); } long long L = l, R = r; for(;l < r; l >>= 1, r >>= 1){ if(l & 1) apply_lazy(l++,f); if(r & 1) apply_lazy(--r,f); } l = L, r = R; for(int h = 1; h <= log; h++){ if(((l >> h) << h) != l) pull_dat(l >> h); if(((r >> h) << h) != r) pull_dat((r-1) >> h); } } //[l,r)で二項演算を作用した結果(0-indexed),O(logN) X prod(long long l, long long r){ if(l == r) return ex; l += n, r += n; for(int h = log; h >= 1; h--){ if(((l >> h) << h) != l) push_lazy(l >> h); if(((r >> h) << h) != r) push_lazy(r >> h); } X vleft = ex, vright = ex; for(; l < r; l >>= 1, r >>= 1){ if(l & 1) vleft = fx(vleft,dat[l++]); if(r & 1) vright = fx(dat[--r],vright); } return fx(vleft,vright); } X all_prod(){return dat[1];}; //x=prod(l,r),f(x)=trueとなる最大のrを求める(f(ex)=true, 0-indexed),O(logN) long long max_right(function<bool(X)> f, long long l = 0){ if(l == N) return N; l += n; push_lazy_deep(l); X sum = ex; do{ while(l % 2 == 0) l >>= 1; if(!f(fx(sum,dat[l]))){ while(l < n){ push_lazy(l); l *= 2; if(f(fx(sum,dat[l]))){ sum = fx(sum,dat[l]); l++; } } return l - n; } sum = fx(sum,dat[l]); l++; }while((l & -l) != l); return N; } //x=prod(l,r),f(x)=trueとなる最小のlを求める(f(ex)=true, 0-indexed),O(logN) long long min_left(function<bool(X)> f, long long r = -1){ if(r == 0) return 0; if(r == -1) return N; r += n; push_lazy_deep(r-1); X sum = ex; do{ r--; while(r > 1 && (r % 2)) r >>= 1; if(!f(fx(dat[r],sum))){ while(r < n){ push_lazy(r); r *= 2; if(f(fx(dat[r],sum))){ sum = fx(dat[r],sum); r--; } } return r + 1 - n; } sum = fx(dat[r],sum); }while((r & -r) != r); return 0; } }; template <typename X> struct SegTree{ using FX = function<X(X,X)>; //Xを2つ受け取りXを返す関数の型 long long n,N; FX fx; X ex; vector<X> dat; //要素数N,二項演算fx,単位元ex; SegTree(long long _n, FX _fx, X _ex){ init(_n, _fx, _ex); } void init(long long _n, FX _fx, X _ex){ N = _n, fx = _fx; ex = _ex; long long x = 1; while(_n > x) x *= 2; n = x; dat.assign(n*2,_ex); } //i番目の要素にアクセス(0-indexed),O(1) X operator[](long long i){return dat[n+i];} X get(long long i){return dat[n+i];} //i番目の要素をxにアップデート(0-indexed),O(logN) void set(long long i, X x){ i += n; dat[i] = x; while(i >>= 1){ dat[i] = fx(dat[2*i],dat[2*i+1]); } } //[l,r)で二項演算を作用した結果(0-indexed),O(logN) X prod(long long l, long long r){ X vleft = ex, vright = ex; for(long long left = l+n, right = r+n; left < right; left >>= 1, right >>= 1){ if(left & 1) vleft = fx(vleft,dat[left++]); if(right & 1) vright = fx(dat[--right],vright); } return fx(vleft,vright); } //[0,N)まで二項演算を作用,O(1) X all_prod() {return dat[1];} //x=prod(l,r),f(x)=trueとなる最大のrを求める(f(ex)=true, 0-indexed),O(logN) long long max_right(const function<bool(X)> f, long long l = 0){ if(l == N) return N; l += n; X sum = ex; do{ while(l % 2 == 0) l >>= 1; if(!f(fx(sum,dat[l]))){ while(l < n){ l = l * 2; if(f(fx(sum,dat[l]))){ sum = fx(sum,dat[l]); l++; } } return l - n; } sum = fx(sum,dat[l]); l++; }while((l & -l) != l); return N; } //x=prod(l,r),f(x)=trueとなる最小のlを求める(f(ex)=true, 0-indexed),O(logN) long long min_left(const function<bool(X)> f, long long r = -1){ if(r == 0) return 0; if(r == -1) return N; r += n; X sum = ex; do{ r--; while(r > 1 && (r % 2)) r >>= 1; if(!f(fx(dat[r],sum))){ while(r < n){ r = r * 2 + 1; if(f(fx(dat[r],sum))){ sum = fx(dat[r],sum); r--; } } return r + 1 - n; } sum = fx(dat[r],sum); }while((r & -r) != r); return 0; } }; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); ll N,M; cin >> N >> M; VL a(N),l(N),r(N); for(ll i = 0; i < N; i++){ cin >> a[i] >> l[i] >> r[i]; l[i]--,r[i]--; } auto f = [](ll x1, ll x2){ return x1+x2; }; ll e = 0; SegTree<ll> seg(M,f,e); using X = PLL; using T = ll; auto fx = [](X x1, X x2){ return X{x1.first+x2.first,x1.second+x2.second}; }; X ex = {0,0}; auto mapping = [](T t, X x){ return X{x.first+t*x.second,x.second}; }; auto comp = [](T t1, T t2){ return t1+t2; }; T et = 0; LazySegTree<X,T> minus(M,fx,mapping,comp,ex,et),other(M,fx,mapping,comp,ex,et); for(ll i = 0; i < M; i++) minus.set(i,{0,1}); for(ll i = 0; i < M; i++) other.set(i,{0,1}); for(ll i = 0; i < N; i++) seg.set(i,a[i]); ll ans = 0; for(ll i = 0; i < N; i++){ minus.apply(l[i],r[i]+1,1); other.apply(l[i],r[i]+1,a[i]); } //for(ll i = 0; i < M; i++) cout << minus[i].first << " "; //cout << '\n'; for(ll i = 0; i < N; i++){ ans += (r[i]-l[i]+1)*a[i]; ans -= a[i]*minus[i].first; } //cout << ans << '\n'; VL now(N,0); iota(ALL(now),0); ll Q; cin >> Q; while(Q--){ ll X,Y,U,V; cin >> X >> Y >> U >> V; X--,Y--,U--,V--; ans -= (r[X]-l[X]+1)*a[X]; ans += a[X]*minus[now[X]].first; //minus.apply(l[X],r[X]+1,-1); other.apply(l[X],r[X]+1,-a[X]); seg.set(now[X],0); { PLL m = other[now[X]]; ll p = seg.prod(l[X],r[X]+1); //if(l[X] <= now[X] and now[X] <= r[X]) m.first -= a[X]; ans += p; } minus.apply(l[X],r[X]+1,-1); minus.apply(U,V+1,1); ans += (V-U+1)*a[X]; ans -= a[X]*minus[Y].first; { PLL m = other[Y]; ll p = seg.prod(U,V+1); //if(l[X] <= Y and Y <= r[X]) m.first -= a[X]; ans -= p; } //minus.apply(U,V+1,1); seg.set(Y,a[X]); other.apply(U,V+1,a[X]); now[X] = Y; l[X] = U, r[X] = V; cout << ans << '\n'; } }