fork download
copy 
  1. #import sys
  2. mod=(10**9)+7
  3. from sys import stdin, stdout
  4. #sys.setrecursionlimit(10**6)
  5. #import threading
  6. #threading.stack_size(2**26)
  7. def ain():
  8.     return map(int,sin().split())
  9. def sin():
  10.     return stdin.readline().strip()
  11. """**************************************************************************"""
  12. def lc(x):
  13.     return (2*x)+1
  14. def rc(x):
  15.     return (2*x)+2
  16. def update(i,l,r,cl,cr,v):
  17.     if(l>r or l>cr or r<cl):
  18.         return
  19.     if(laz[i]!=[1,0]):
  20.         s[i]=(s[i]*laz[i][0])%mod
  21.         s[i]=(s[i]+(laz[i][1]*(r-l+1))%mod)%mod
  22.         if(l!=r):
  23.             laz[lc(i)][0]=(laz[lc(i)][0]*laz[i][0])%mod
  24.             laz[lc(i)][1]=(laz[lc(i)][1]*laz[i][0])%mod
  25.             laz[lc(i)][1]=(laz[lc(i)][1]+laz[i][1])%mod
  26.             laz[rc(i)][0]=(laz[rc(i)][0]*laz[i][0])%mod
  27.             laz[rc(i)][1]=(laz[rc(i)][1]*laz[i][0])%mod
  28.             laz[rc(i)][1]=(laz[rc(i)][1]+laz[i][1])%mod
  29.         laz[i]=[1,0]
  30.     if(l>=cl and r<=cr):
  31.         s[i]=(s[i]*v[0])%mod
  32.         s[i]=(s[i]+(v[1]*(r-l+1))%mod)%mod
  33.         if(l!=r):
  34.             laz[lc(i)][0]=(laz[lc(i)][0]*v[0])%mod
  35.             laz[lc(i)][1]=(laz[lc(i)][1]*v[0])%mod
  36.             laz[lc(i)][1]=(laz[lc(i)][1]+v[1])%mod
  37.             laz[rc(i)][0]=(laz[rc(i)][0]*v[0])%mod
  38.             laz[rc(i)][1]=(laz[rc(i)][1]*v[0])%mod
  39.             laz[rc(i)][1]=(laz[rc(i)][1]+v[1])%mod
  40.         return
  41.     mid=(l+r)/2
  42.     update(lc(i),l,mid,cl,cr,v)
  43.     update(rc(i),mid+1,r,cl,cr,v)
  44.     s[i]=(s[lc(i)]+s[rc(i)])%mod
  45. def range1(i,l,r,cl,cr):
  46.     if(l>r or l>cr or r<cl):
  47.         return 0
  48.     if(laz[i]!=[1,0]):
  49.         s[i]=(s[i]*laz[i][0])%mod
  50.         s[i]=(s[i]+(laz[i][1]*(r-l+1))%mod)%mod
  51.         if(l!=r):
  52.             laz[lc(i)][0]=(laz[lc(i)][0]*laz[i][0])%mod
  53.             laz[lc(i)][1]=(laz[lc(i)][1]*laz[i][0])%mod
  54.             laz[lc(i)][1]=(laz[lc(i)][1]+laz[i][1])%mod
  55.             laz[rc(i)][0]=(laz[rc(i)][0]*laz[i][0])%mod
  56.             laz[rc(i)][1]=(laz[rc(i)][1]*laz[i][0])%mod
  57.             laz[rc(i)][1]=(laz[rc(i)][1]+laz[i][1])%mod
  58.         laz[i]=[1,0]
  59.     if(l>=cl and r<=cr):
  60.             return s[i]
  61.     mid=(l+r)/2
  62.     p1=range1(lc(i),l,mid,cl,cr)
  63.     p2=range1(rc(i),mid+1,r,cl,cr)
  64.     return (p1+p2)%mod
  65. n,q=ain()
  66. a=ain()
  67. k=set(a)
  68. b=[]
  69. for i in range(q):
  70.     l,r,x,y=ain()
  71.     k.add(l)
  72.     k.add(r)
  73.     b.append([l,r,x%mod,y%mod])
  74. f=list(k)
  75. f.sort()
  76. d={}
  77. for i in range(len(f)):
  78.     d[f[i]]=i
  79. s=[0]*(4*len(f))
  80. laz=[[1,0] for i in range(4*len(f))]
  81. for i in range(q):
  82.     update(0,0,len(f)-1,d[b[i][0]],d[b[i][1]],[b[i][2],b[i][3]])
  83. ans=[]
  84. for i in range(n):
  85.     x=range1(0,0,len(f)-1,d[a[i]],d[a[i]])
  86.     ans.append(str(x))
  87. stdout.write(" ".join(ans))
Success #stdin #stdout 0.01s 7312KB
comments (?)
stdin
copy 
2 2
1 2
1 3 2 3
1 3 2 4
stdout
copy 
10 10
https://ideone.com/Qxoy6X
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!