Sort by

recency

|

24 Discussions

|

  • + 0 comments

    I think the times may need to be tightened; the naive O(nq) solution gets full points when implemented in C.

  • + 0 comments

    Python3 solution

    import sys
    
    M = 1000003
    F = [1] * M
    for i in range(1, M): 
        F[i] = (i * F[i-1]) % M
        
    def f(i): 
        return F[i] if i < M else 0
    
    def build(a, i, j):
        if i + 1 == j:
            return (i, j, None, None, a[i][1], a[i][1], a[i][0], pow(a[i][0], a[i][1], M))
        l = build(a, i, (i + j) // 2)
        r = build(a, (i + j) // 2, j)
        K = l[5] + r[5]
        d = (l[6] * r[6]) % M
        V = (l[7] * r[7]) % M
        return (i, j, l, r, 0, K, d, V)
    
    def update(t,i,j,p):
        ti, tj, tl, tr, tp, tK, td, tV = t
        if tj <= i or j <= ti: return t, 0, 1
        if i <= ti and tj <= j:
            tp += p
            dk = (tj - ti) * p
            dv = pow(td, p, M) if dk < M else 0
        else:
            tl, lk, lv = update(tl, i, j, p) if tl != None else (tl, 0, 1)
            tr, rk, rv = update(tr, i, j, p) if tr != None else (tr, 0, 1)
            dk, dv = lk + rk, (lv * rv) % M
        tK += dk
        tV = (tV * dv) % M
        return (ti, tj, tl, tr, tp, tK, td, tV), dk, dv
    
    def queryK(t, i, j, p = 0):
        ti, tj, tl, tr, tp, tK, td, tV = t
        if tj < i or j < ti: return 0
        if i <= ti and tj <= j: return tK + (tj - ti) * p
        lk = queryK(tl, i, j, p + tp) if tl != None else 0
        rk = queryK(tr, i, j, p + tp) if tr != None else 0
        return lk + rk
    
    def queryV(t, i, j, p = 0):
        ti, tj, tl, tr, tp, tK, td, tV = t
        if tj < i or j < ti: return 1
        if i <= ti and tj <= j: return (tV * pow(td, p, M)) % M
        lv = queryV(tl, i, j, p + tp) if tl != None else 1
        rv = queryV(tr, i, j, p + tp) if tr != None else 1
        return (lv * rv) % M
    
    n = int(sys.stdin.readline())
    a = [list(map(int,sys.stdin.readline().split()[1:])) for i in range(n)]
    T = build(a, 0, len(a))
    for q in range(int(sys.stdin.readline())):
        x = list(map(int,sys.stdin.readline().split()))
        if x[0]:
            T = update(T, x[1] - 1, x[2], x[3])[0]
        else:
            k = queryK(T, x[1] - 1, x[2])
            v = queryV(T, x[1] - 1, x[2]) if k < M else 0
            print('%d %d'%(k, (v * f(k)) % M))
    
  • + 0 comments

    for complete solution in python java c++ and c programming search for programs.programmingoneonone.com on google

  • + 1 comment
    #include <cstdio>
    #include <utility>
    using namespace std;
    
    typedef long long ll;
    #define FOR(i, a, b) for (int i = (a); i < (b); i++)
    #define REP(i, n) for (int i = 0; i < (n); i++)
    #define ROF(i, a, b) for (int i = (b); --i >= (a); )
    #define fi first
    #define se second
    
    int ri()
    {
      int x;
      scanf("%d", &x);
      return x;
    }
    
    const int N = 100000, NN = 131072, MOD = 1000003;
    ll fact[MOD], d[2*NN], p[2*NN], dp[2*NN], dlt[2*NN];
    
    ll power(ll a, int n)
    {
      ll r = 1;
      for (; n; n >>= 1, a = a*a%MOD)
        if (n & 1)
          r = r*a%MOD;
      return r;
    }
    
    void apply(int n, int i, ll v)
    {
      dlt[i] += v;
      p[i] += v << __builtin_clz(i)-__builtin_clz(n);
      dp[i] = dp[i]*power(d[i], v)%MOD;
    }
    
    void mconcat(int i)
    {
      p[i] = p[2*i]+p[2*i+1];
      dp[i] = dp[2*i]*dp[2*i+1]%MOD;
    }
    
    void untag(int n, int i)
    {
      if (i < 0 || n <= i) return;
      i += n;
      for (int j, h = 31-__builtin_clz(n); h; h--)
        if (dlt[j = i >> h]) {
          apply(n, 2*j, dlt[j]);
          apply(n, 2*j+1, dlt[j]);
          dlt[j] = 0;
        }
    }
    
    void add(int n, int l, int r, ll v)
    {
      bool lf = false, rf = false;
      untag(n, l-1);
      untag(n, r);
      for (l += n, r += n; l < r; ) {
        if (l & 1) lf = true, apply(n, l++, v);
        l >>= 1;
        if (lf) mconcat(l-1);
        if (r & 1) rf = true, apply(n, --r, v);
        r >>= 1;
        if (rf) mconcat(r);
      }
      for (l--; l >>= 1, r >>= 1; ) {
        if (lf || l == r) mconcat(l);
        if (rf && l != r) mconcat(r);
      }
    }
    
    pair<ll, ll> query(int n, int l, int r)
    {
      ll ps = 0, dps = 1;
      untag(n, l-1);
      untag(n, r);
      for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) {
          ps += p[l];
          dps = dps*dp[l]%MOD;
          l++;
        }
        if (r & 1) {
          r--;
          ps += p[r];
          dps = dps*dp[r]%MOD;
        }
      }
      return {ps, dps};
    }
    
    int main()
    {
      fact[0] = 1;
      FOR(i, 1, MOD)
        fact[i] = fact[i-1]*i%MOD;
      int n = ri(), nn = 1;
      while (nn < n) nn *= 2;
      REP(i, n) {
        ri();
        d[nn+i] = ri();
        p[nn+i] = ri();
        dp[nn+i] = power(d[nn+i], p[nn+i]);
      }
      ROF(i, 1, nn) {
        d[i] = d[2*i]*d[2*i+1]%MOD;
        mconcat(i);
      }
      for (int q = ri(); q--; ) {
        int op = ri(), l = ri()-1, r = ri();
        if (op)
          add(nn, l, r, ri());
        else {
          auto ans = query(nn, l, r);
          ll ps = ans.fi, dps = (ans.se+MOD)%MOD;
          printf("%lld %lld\n", ps, ps >= MOD ? 0 : fact[ps]*dps%MOD);
        }
      }
    }
    
  • + 0 comments

    In the last operation "0 1 1", from the given example,

    It is given as updated secquence => 1 9 25 49 81 (after update) second second => 1 9 25 49 81 (after update) Why the two progressions NOT multiplied?