結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:45:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,154 ms / 2,500 ms |
コード長 | 5,048 bytes |
コンパイル時間 | 4,188 ms |
コンパイル使用メモリ | 258,020 KB |
実行使用メモリ | 16,168 KB |
最終ジャッジ日時 | 2025-09-06 14:46:38 |
合計ジャッジ時間 | 31,878 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
# include <bits/stdc++.h> # include <atcoder/modint> # include <atcoder/segtree> # include <atcoder/lazysegtree> # include <atcoder/dsu> # include <atcoder/scc> # include <atcoder/string> # include <atcoder/twosat> # include <atcoder/math> # include <atcoder/convolution> //# include <regex> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<vector<vector<int>>> vvvi; typedef vector<long long> vl; typedef vector<vector<long long>> vvl; typedef vector<vector<vector<long long>>> vvvl; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef vector<vector<vector<bool>>> vvvb; #define rep(i,n) for(int i=0;i<n;i++) #define reps(i,m,n) for(int i=m;i<n;i++) #define repl(i,n) for(ll i=0;i<n;i++) #define repsl(i,m,n) for(ll i=m;i<n;i++) #define repr(i,n) for(int i=n-1;i>=0;i--) #define repsr(i,m,n) for(int i=n-1;i>=m;i--) #define replr(i,n) for(ll i=n-1;i>=0;i--) #define repslr(i,m,n) for(ll i=n-1;i>=m;i--) #define sksort(x) sort(x.begin(), x.end()) #define sksortr(x) sort(x.rbegin(), x.rend()) #define disp(x) cout << x << endl #define disps(x) cout << x << " " #define dispe cout << endl #define dispv(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj]);}dispe #define dispvv(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispv(x[xqzi]);} #define dispvm(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj].val());}dispe #define dispvvm(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispvm(x[xqzi]);} #define dispy cout << "Yes" << endl #define dispn cout << "No" << endl #define dispyn(x) if(x)dispy;else dispn #define dispd cout << std::setprecision(20) #define inp(x) int x;cin>>x #define inpl(x) ll x;cin>>x #define inps(x) string x;cin>>x #define allv(x) (x).begin(),(x).end() #define allrv(x) (x).rbegin(),(x).rend() #define imax(x,y) x=max(x,y) #define imin(x,y) x=min(x,y) template <class T> using priority_queue_asc = std::priority_queue<T,std::vector<T>,std::greater<T>>; using mint = atcoder::modint998244353; //using mint = atcoder::modint1000000007; template <class S, S (*op)(S, S), S (*e)()> class dual_segtree { public: dual_segtree() : dual_segtree(0) {} explicit dual_segtree(int n) : dual_segtree(std::vector<S>(n, e())) {} explicit dual_segtree(const std::vector<S>& v) : _n(int(v.size())) { size = bit_ceil((unsigned int)(_n)); log = __builtin_ctz(size); memory = std::vector<std::vector<S>>(log+1); for(int i=0;i<=log;i++) memory[i] = std::vector<S>(1<<(log-i), e()); for(int i=0;i<=_n;i++) memory[0][i] = v[i]; } template <class F> void apply(unsigned long long l, unsigned long long r, const F& f) { if(l >= r) return; unsigned long long mask = l ^ r; mask >>= 1; mask |= (mask >> 1); mask |= (mask >> 2); mask |= (mask >> 4); mask |= (mask >> 8); mask |= (mask >> 16); mask |= (mask >> 32); unsigned long long wl = ((l & mask) ^ mask) + 1ULL; unsigned long long wr = r & mask; unsigned int q = 0; while(wl){ if(wl&1ULL) memory[q][l] = f(memory[q][l]); l >>= 1; if(wl&1ULL) l++; wl >>= 1; q++; } q = 0; while(wr){ if(wr&1ULL) memory[q][r-1] = f(memory[q][r-1]); r >>= 1; wr >>= 1; q++; } } S get(unsigned long long p){ unsigned int c = 0; S r = e(); while(p || c < memory.size()){ if(c < memory.size()) r = op(r, memory[c][p]); else r = op(r, e()); p >>= 1; c++; } return r; } private: int _n, size, log; std::vector<std::vector<S>> memory; unsigned int bit_ceil(unsigned int n) { unsigned int x = 1; while (x < n) x <<= 1; return x; } }; ll op1(ll l, ll r){ return l+r; } ll e1(){ return 0; } ll op2(ll l, ll r){ return l+r; } ll e2(){ return 0; } int main(){ inp(n); inp(m); vl a(n); vi l(n),r(n); rep(i,n)cin>>a[i]>>l[i]>>r[i]; dual_segtree<ll,op1,e1> seg1(m); atcoder::segtree<ll,op2,e2> seg2(m); ll ans=0; rep(i,n){ seg1.apply(l[i]-1,r[i],[](ll x){return x+1;}); seg2.set(i,a[i]); ans+=(r[i]-l[i]+1)*a[i]; } rep(i,n)ans-=seg1.get(i)*a[i]; inp(q); vi p(n); rep(i,n)p[i]=i; while(q--){ inp(x); inp(y); inp(u); inp(v); seg1.apply(l[x-1]-1,r[x-1],[](ll x){return x-1;}); ans+=seg2.prod(l[x-1]-1,r[x-1]); seg2.set(p[x-1],0); ans-=(r[x-1]-l[x-1]+1)*a[x-1]; ans+=seg1.get(p[x-1])*a[x-1]; l[x-1]=u; r[x-1]=v; p[x-1]=y-1; ans-=seg1.get(p[x-1])*a[x-1]; ans+=(r[x-1]-l[x-1]+1)*a[x-1]; seg2.set(p[x-1],a[x-1]); ans-=seg2.prod(l[x-1]-1,r[x-1]); seg1.apply(l[x-1]-1,r[x-1],[](ll x){return x+1;}); disp(ans); } }