API tools faq
paste
Advertisement
jedrzejd

Untitled

jedrzejd
Apr 8th, 2019
117
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.13 KB | None | 0 0
raw download clone embed print report
  1. //
  2. //  main.cpp
  3. //  Iloczyn skalarny
  4. //
  5. //  Created by Jędrzej Dudzicz on 07/04/2019.
  6. //  Copyright © 2019 Jędrzej Dudzicz. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <cstdio>
  11. #include <algorithm>
  12. #include <utility>
  13. #include <cmath>
  14. using namespace std;
  15. typedef long long LL;
  16. const int MXN=1e5+5;
  17. const int PIER=260;
  18. const LL MOD=1e9+7;
  19. struct wezel{
  20.     int asum,bsum;
  21.     int wynik,acaly,bcaly;
  22. };
  23. int n,q;
  24. int indeks[MXN];
  25. wezel pom[MXN];
  26. char znak;
  27. int a,b,c,nr_paczki;
  28. LL tab[MXN][3];
  29. int main(){
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(0);
  32.     cout.tie(0);
  33.     cin>>n>>q;
  34.     for(int i=1;i<=n;i++){
  35.         if((i-1)%PIER==0){
  36.             nr_paczki++;
  37.         }
  38.         indeks[i]=nr_paczki;
  39.     }
  40.     for(int i=0;i<=nr_paczki;i++){
  41.         pom[i].wynik=0;
  42.         pom[i].asum=0;
  43.         pom[i].bsum=0;
  44.         pom[i].acaly=0;
  45.         pom[i].bcaly=0;
  46.     }
  47.     for(int ii=0;ii<q;ii++){
  48.         cin>>znak;
  49.         if(znak=='*'){//               ( A )
  50.             cin>>a>>b>>c;
  51.             if(indeks[a]==indeks[b]){
  52.                 int curr=indeks[a];
  53.                 int ind1,ind2,p1,k1;
  54.                 pom[curr].wynik=0;
  55.                 p1=(curr-1)*PIER+1;
  56.                 k1=(curr)*PIER;
  57.                 for(int i=p1;i<=k1;i++)tab[i][1]=tab[i][1]%MOD+pom[curr].bcaly;
  58.                 pom[curr].bcaly=0;
  59.                 for(int i=p1;i<=k1;i++)tab[i][0]=tab[i][0]%MOD+pom[curr].acaly;
  60.                 ind1=a;
  61.                 ind2=b;
  62.                 for(int i=ind1;i<=ind2;i++)tab[i][0]=(tab[i][0]+c)%MOD;
  63.                 for(int i=p1;i<=k1;i++){
  64.                     pom[curr].wynik=pom[curr].wynik%MOD+(tab[i][0]*tab[i][1])%MOD;
  65.                     pom[curr].asum=pom[curr].asum%MOD+tab[i][0];
  66.                 }
  67.                 pom[curr].acaly=0;
  68.             }
  69.             else if(indeks[a]!=indeks[b]){
  70.                 int curr=indeks[a],curr1=indeks[b];
  71.                 int ind1,ind2,p1,k1;
  72.                 pom[curr].wynik=0;
  73.                 p1=(curr-1)*PIER+1;
  74.                 k1=(curr)*PIER;
  75.                 for(int i=p1;i<=k1;i++)tab[i][1]=tab[i][1]%MOD+pom[curr].bcaly;
  76.                 pom[curr].bcaly=0;
  77.                 for(int i=p1;i<=k1;i++)tab[i][0]=tab[i][0]%MOD+pom[curr].acaly;
  78.                 ind1=a;
  79.                 ind2=(curr)*PIER;
  80.                 for(int i=ind1;i<=ind2;i++)tab[i][0]=(tab[i][0]+c)%MOD;
  81.                 for(int i=p1;i<=k1;i++){
  82.                     //cout<<tab[i][0]<<" ";
  83.                     pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  84.                     pom[curr].asum=pom[curr].asum%MOD+tab[i][0];
  85.                 }
  86.                 pom[curr].acaly=0;
  87.                 //cout<<"ind1: "<<ind1<<" ind2: "<<ind2<<" p1: "<<p1<<" k1: "<<k1<<endl;
  88.                 //cout<<"curr: "<<curr<<" curr1: "<<curr1<<endl;
  89.                 //cout<<"A sum: "<<pom[curr].asum<<" A Caly: "<<pom[curr].acaly<<" Wynik: "<<pom[curr].wynik<<endl;
  90.                 curr++;
  91.                 while(curr<curr1){
  92.                     pom[curr].asum=(pom[curr].asum+c*PIER)%MOD;
  93.                     pom[curr].acaly=(pom[curr].acaly+c)%MOD;
  94.                     pom[curr].wynik=(pom[curr].wynik+pom[curr].bsum*c)%MOD;
  95.                 //    cout<<"A sum: "<<pom[curr].asum<<" A Caly: "<<pom[curr].acaly<<" Wynik: "<<pom[curr].wynik<<endl;
  96.                 //    cout<<"curr: "<<curr<<" curr1: "<<curr1<<endl;
  97.                     curr++;
  98.                 }
  99.                 if(curr==curr1){
  100.                     pom[curr].wynik=0;
  101.                     p1=(curr-1)*PIER+1;
  102.                     k1=(curr)*PIER;
  103.                     for(int i=p1;i<=k1;i++)tab[i][0]=tab[i][0]%MOD+pom[curr].acaly;
  104.                     for(int i=p1;i<=k1;i++)tab[i][1]=tab[i][1]%MOD+pom[curr].bcaly;
  105.                     pom[curr].bcaly=0;
  106.                     ind1=(curr-1)*PIER+1;
  107.                     ind2=b;
  108.                     for(int i=ind1;i<=ind2;i++)tab[i][0]=(tab[i][0]+c)%MOD;
  109.                     for(int i=p1;i<=k1;i++){
  110.                         //cout<<tab[i][0]<<" ";
  111.                         pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  112.                         pom[curr].asum=(pom[curr].asum+tab[i][0])%MOD;
  113.                     }
  114.                     pom[curr].acaly=0;
  115.               //      cout<<"A sum: "<<pom[curr].asum<<" A Caly: "<<pom[curr].acaly<<" Wynik: "<<pom[curr].wynik<<endl;
  116.               //      cout<<"ind1: "<<ind1<<" ind2: "<<ind2<<" p1: "<<p1<<" k1: "<<k1<<endl;
  117.               //      cout<<"curr: "<<curr<<" curr1: "<<curr1<<endl;
  118.                 }
  119.             }
  120.         }
  121.         else if(znak=='.'){//         ( B )
  122.             cin>>a>>b>>c;
  123.             if(indeks[a]==indeks[b]){
  124.                 int curr=indeks[a];
  125.                 int ind1,ind2,p1,k1;
  126.                 pom[curr].wynik=0;
  127.                 p1=(curr-1)*PIER+1;
  128.                 k1=(curr)*PIER;
  129.                 for(int i=p1;i<=k1;i++)tab[i][0]=(tab[i][0]+pom[curr].acaly)%MOD;
  130.                 pom[curr].acaly=0;
  131.                 for(int i=p1;i<=k1;i++)tab[i][1]=(tab[i][1]+pom[curr].bcaly)%MOD;
  132.                 ind1=a;
  133.                 ind2=b;
  134.                 for(int i=ind1;i<=ind2;i++)tab[i][1]=(tab[i][1]+c)%MOD;
  135.                 for(int i=p1;i<=k1;i++){
  136.                     pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  137.                     pom[curr].bsum=(pom[curr].bsum+tab[i][1])%MOD;
  138.                 }
  139.                 pom[curr].bcaly=0;
  140.             }
  141.             else if(indeks[a]!=indeks[b]){
  142.                 int curr=indeks[a],curr1=indeks[b];
  143.                 int ind1,ind2,p1,k1;
  144.                 pom[curr].wynik=0;
  145.                 p1=(curr-1)*PIER+1;
  146.                 k1=(curr)*PIER;
  147.                 for(int i=p1;i<=k1;i++)tab[i][0]=(tab[i][0]+pom[curr].acaly)%MOD;
  148.                 pom[curr].acaly=0;
  149.                 for(int i=p1;i<=k1;i++)tab[i][1]=(tab[i][1]+pom[curr].bcaly)%MOD;
  150.                 ind1=a;
  151.                 ind2=(curr)*PIER;
  152.                 for(int i=ind1;i<=ind2;i++)tab[i][1]=(tab[i][1]+c)%MOD;
  153.                 for(int i=p1;i<=k1;i++){
  154.            //         cout<<tab[i][0]<<" ";
  155.                     pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  156.                     pom[curr].bsum=(pom[curr].bsum+tab[i][1])%MOD;
  157.                 }
  158.                 pom[curr].bcaly=0;
  159.             //    cout<<"ind1: "<<ind1<<" ind2: "<<ind2<<" p1: "<<p1<<" k1: "<<k1<<endl;
  160.             //    cout<<"curr: "<<curr<<" curr1: "<<curr1<<endl;
  161.             //    cout<<"B sum: "<<pom[curr].bsum<<" B Caly: "<<pom[curr].bcaly<<" Wynik: "<<pom[curr].wynik<<endl;
  162.                 curr++;
  163.                 while(curr<curr1){
  164.                     pom[curr].bsum=(pom[curr].bsum+c*PIER)%MOD;
  165.                     pom[curr].bcaly=(pom[curr].bcaly+c)%MOD;
  166.                     pom[curr].wynik=(pom[curr].wynik+pom[curr].asum*c)%MOD;
  167.             //        cout<<"ind1: "<<ind1<<" ind2: "<<ind2<<" p1: "<<p1<<" k1: "<<k1<<endl;
  168.             //        cout<<"curr: "<<curr<<" curr1: "<<curr1<<endl;
  169.             //        cout<<"B sum: "<<pom[curr].bsum<<" B Caly: "<<pom[curr].bcaly<<" Wynik: "<<pom[curr].wynik<<endl;
  170.                     curr++;
  171.                 }
  172.                 if(curr==curr1){
  173.                     pom[curr].wynik=0;
  174.                     p1=(curr-1)*PIER+1;
  175.                     k1=(curr)*PIER;
  176.                     for(int i=p1;i<=k1;i++)tab[i][0]=(tab[i][0]+pom[curr].acaly)%MOD;
  177.                     pom[curr].acaly=0;
  178.                     for(int i=p1;i<=k1;i++)tab[i][1]=(tab[i][1]+pom[curr].bcaly)%MOD;
  179.                     ind1=p1;
  180.                     ind2=b;
  181.                     for(int i=ind1;i<=ind2;i++)tab[i][1]=(tab[i][1]+c)%MOD;
  182.                     for(int i=p1;i<=k1;i++){
  183.                         pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  184.                         pom[curr].bsum=(pom[curr].bsum+tab[i][1])%MOD;
  185.                     }
  186.                     pom[curr].bcaly=0;
  187.             //        cout<<"ind1: "<<ind1<<" ind2: "<<ind2<<" p1: "<<p1<<" k1: "<<k1<<endl;
  188.             //        cout<<"curr: "<<curr<<" curr1: "<<curr1<<endl;
  189.             //        cout<<"B sum: "<<pom[curr].bsum<<" B Caly: "<<pom[curr].bcaly<<" Wynik: "<<pom[curr].wynik<<endl;
  190.                 }
  191.             }
  192.         }
  193.         else{
  194.             cin>>a>>b;
  195.             LL ans=0;
  196.             int curr=indeks[a],curr1=indeks[b];
  197.             int ind1,ind2,p1,k1;
  198.             if(curr==curr1){
  199.                
  200.                 pom[curr].wynik=0;
  201.                 p1=(curr-1)*PIER+1;
  202.                 k1=(curr)*PIER;
  203.                 for(int i=p1;i<=k1;i++){
  204.                     tab[i][0]=(tab[i][0]+pom[curr].acaly)%MOD;
  205.                     tab[i][1]=(tab[i][1]+pom[curr].bcaly)%MOD;
  206.                 }
  207.                 ind1=a;
  208.                 ind2=b;
  209.                 //cout<<ind1<<" "<<ind2<<endl;
  210.                 for(int i=p1;i<=k1;i++){
  211.                     pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  212.                 }
  213.                 pom[curr].acaly=0;
  214.                 pom[curr].bcaly=0;
  215.                
  216.                 //cout<<ind1<<" "<<ind2<<endl;
  217.                 for(int i=ind1;i<=ind2;i++){
  218.                     ans=ans%MOD+(tab[i][0]*tab[i][1])%MOD;
  219.                 //    cout<<tab[i][1]<<" ";
  220.                 }
  221.             }
  222.             else if(curr!=curr1){
  223.                
  224.                 pom[curr].wynik=0;
  225.                 p1=(curr-1)*PIER+1;
  226.                 k1=(curr)*PIER;
  227.                 for(int i=p1;i<=k1;i++){
  228.                     tab[i][0]=(tab[i][0]+pom[curr].acaly)%MOD;
  229.                     tab[i][1]=(tab[i][1]+pom[curr].bcaly)%MOD;
  230.                 }
  231.                 ind1=a;
  232.                 ind2=(curr)*PIER;
  233.                 //cout<<ind1<<" "<<ind2<<endl;
  234.                 for(int i=p1;i<=k1;i++){
  235.                     pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  236.                 }
  237.                 pom[curr].acaly=0;
  238.                 pom[curr].bcaly=0;
  239.  
  240.                 for(int i=ind1;i<=ind2;i++){
  241.                     ans=ans%MOD+(tab[i][0]*tab[i][1])%MOD;
  242.                     //cout<<tab[i][0]<<" ";
  243.                 }
  244.                 curr++;
  245.                 while(curr<curr1){
  246.                     ans=(ans%MOD+pom[curr].wynik%MOD)%MOD;
  247.                     curr++;
  248.                 }
  249.                 if(curr==curr1){
  250.                    
  251.                     pom[curr].wynik=0;
  252.                     p1=(curr-1)*PIER+1;
  253.                     k1=(curr)*PIER;
  254.                     for(int i=p1;i<=k1;i++){
  255.                         tab[i][0]=(tab[i][0]+pom[curr].acaly)%MOD;
  256.                         tab[i][1]=(tab[i][1]+pom[curr].bcaly)%MOD;
  257.                     }
  258.                     ind1=(curr-1)*PIER+1;
  259.                     ind2=b;
  260.                     for(int i=p1;i<=k1;i++){
  261.                         pom[curr].wynik=(pom[curr].wynik+tab[i][0]*tab[i][1])%MOD;
  262.                     }
  263.                     pom[curr].acaly=0;
  264.                     pom[curr].bcaly=0;
  265.                    
  266.                    
  267.                     //cout<<ind1<<" "<<ind2<<endl;
  268.                     for(int i=ind1;i<=ind2;i++)ans=ans%MOD+(tab[i][0]*tab[i][1])%MOD;
  269.                 }
  270.             }
  271.             cout<<ans%MOD<<endl;
  272.         }
  273.        
  274.     }
  275.     return 0;
  276. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!