제출 #602200

#제출 시각아이디문제언어결과실행 시간메모리
602200inksamuraiRelativnost (COCI15_relativnost)C++17
0 / 140
4082 ms34688 KiB
#include <bits/stdc++.h> // cut here #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder namespace atcoder { template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} segtree(int n) : segtree(std::vector<S>(n, e())) {} segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template <bool (*f)(S)> int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder // cut here using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rng(i,c,n) for(int i=(c);i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define fi first #define se second #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3aFGabX ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} // e const int _c=21; const int mod=10007; struct dat{ int dp[_c+2]{0}; }; dat op(dat l,dat r){ dat res; rep(i,_c){ rep(j,_c){ int k=min(_c,i+j); res.dp[k]+=l.dp[i]*r.dp[j]%mod; res.dp[k]%=mod; } } return res; } dat _e; dat e(){ return _e; } signed main(){ _3aFGabX; _e.dp[0]=1; int n,c; cin>>n>>c; vec(pii) a(n); rep(i,n){ cin>>a[i].fi>>a[i].se; } atcoder::segtree<dat,op,e> seg(n); rep(i,n){ dat now; now.dp[0]=a[i].se%mod; now.dp[1]=a[i].fi%mod; seg.set(i,now); } int q; cin>>q; rep(_,q) { int i,_a,_b; cin>>i>>_a>>_b; i-=1; a[i]={_a,_b}; dat now; now.dp[0]=a[i].se%mod; now.dp[1]=a[i].fi%mod; // print(a[i].fi,a[i].se); seg.set(i,now); // print(seg.prod(0,2).dp[0],seg.prod(0,2).dp[2]); dat res=seg.prod(0,n); int ans=0; rng(i,c,_c+1){ // cout<<res.dp[i]<<" "; ans+=res.dp[i]; ans%=mod; } print(ans); // break; } }
#Verdict Execution timeMemoryGrader output
Fetching results...