fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<math.h>
  6. #include<limits.h>
  7. #include<time.h>
  8. #include<set>
  9. #include<vector>
  10. #include<map>
  11. #include<queue>
  12. #include<stack>
  13. #include<deque>
  14.  
  15. #include<cstring>
  16. #include<string>
  17.  
  18.  
  19. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  20. #define FORD(i,a,b) for(int i=a;i>=b;i--)
  21. #define pb push_back 
  22. #define lli long long int
  23. #define mod1 1000000007
  24. #define mod2 1000000009
  25. #define ppi pair<int,int>
  26. #define tr(a,it) for(typeof(a.begin()) it=a.begin();it!=a.end();it++)
  27.  
  28. using namespace std;
  29.  
  30. int segtree[13][20*100001];
  31. int force[20*100001];
  32. int br[13][20*100001];
  33. int ar[3000001];
  34. vector<int>de[3000001];
  35.  
  36.  
  37. int build(int fr,int node,int f,int l)
  38. {
  39.     force[node]=0;
  40.  
  41.     if(f==l)
  42.     {
  43.             segtree[fr][node]=br[fr][f];
  44.  
  45.             return segtree[fr][node];
  46.     }
  47.  
  48.     int b1=build(fr,2*node,f,(f+l)/2);
  49.     int b2=build(fr,2*node+1,((f+l)/2)+1,l);
  50.  
  51.     segtree[fr][node]=max(b1,b2);
  52.  
  53.     return segtree[fr][node];
  54. }
  55.  
  56. int update(int node,int f,int l,int x,int y,int fr)
  57. {
  58.     if(l<x||y<f||f>l)
  59.     {
  60.     return 0;
  61.     }
  62.  
  63.     int br[2][13];
  64.     if(x<=f&&l<=y)
  65.     {
  66.                   force[node]+=fr;
  67.  
  68.                   FOR(i,0,12)br[0][i]=segtree[i][node];
  69.  
  70.                   FOR(i,0,12)segtree[i][node]=br[0][(i+fr)%12];
  71.  
  72.                   return 0;
  73.     }
  74.  
  75.     force[2*node]=+force[node];
  76.     force[2*node+1]=+force[node];
  77.  
  78.     FOR(i,0,12)
  79.     {
  80.               br[0][i]=segtree[i][2*node];
  81.               br[1][i]=segtree[i][2*node+1];
  82.     }
  83.  
  84.     FOR(i,0,12)
  85.     {
  86.               segtree[i][2*node]=br[0][(i+force[node])%12];
  87.               segtree[i][2*node+1]=br[1][(i+force[node])%12];
  88.     }
  89.  
  90.     force[node]=0;
  91.  
  92.     update(2*node,f,(f+l)/2,x,y,fr);
  93.     update(2*node+1,((f+l)/2)+1,l,x,y,fr);
  94.  
  95.     FOR(i,0,12)segtree[i][node]=max(segtree[i][2*node],segtree[i][2*node+1]);
  96.  
  97.     return 0;
  98. }
  99.  
  100. int query(int node,int f,int l,int x,int y,int fi)
  101. {
  102.       if(l<x||y<f||f>l)return 0;
  103.       else
  104.       if(x <= f &&l <= y)
  105.       {
  106.                   return segtree[(fi)%12][node];
  107.       }
  108.  
  109.       fi+=force[node];
  110.  
  111.       int q1=query(2*node,f,(f+l)/2,x,y,fi);
  112.       int q2=query(2*node+1,((f+l)/2)+1,l,x,y,fi);
  113.  
  114.       return max(q1,q2);
  115. }
  116.  
  117. int main()
  118. {
  119.     //clock_t start=clock();
  120.     int n;
  121.     scanf("%d",&n);
  122.  
  123.     FOR(i,1,n)scanf("%d",&ar[i]);
  124.  
  125.     FOR(i,1,n)
  126.     {
  127.               int x=ar[i];
  128.               while(x>0)
  129.               {
  130.                        de[i].pb(x%10);
  131.                        x=(x-x%10)/10;
  132.               }
  133.  
  134.               FOR(z,0,12)
  135.               {
  136.                int y=0;
  137.  
  138.               int sz=de[i].size();
  139.  
  140.               FORD(j,sz-1,0)
  141.               {
  142.                        y*=10;
  143.                        y+=de[i][(j-z+12*sz)%sz];
  144.  
  145.               }
  146.  
  147.                      br[z][i]=y;
  148.  
  149.               }
  150.     }
  151.  
  152.     FOR(i,0,12)
  153.     {
  154.               build(i,1,1,n);
  155.     }
  156.  
  157.  
  158.     int m;
  159.     scanf("%d",&m);
  160.  
  161.     while(m--)
  162.     {
  163.               int qu;
  164.               scanf("%d",&qu);
  165.  
  166.               int l,r,f;
  167.  
  168.               scanf("%d%d",&l,&r);
  169.  
  170.               if(qu==0)
  171.               {
  172.                  scanf("%d",&f);
  173.                  update(1,1,n,l+1,r+1,f%12);
  174.  
  175.               }
  176.               else
  177.               {
  178.                   printf("%d\n",query(1,1,n,l+1,r+1,0));
  179.               }
  180.     }
  181.  
  182.      //while(clock()-start<0.95*CLOCKS_PER_SEC);
  183.     return 0;
  184. } 
  185.  
Success #stdin #stdout 0.03s 260608KB
comments (?)
stdin
copy 
3
17 3140 832
8
1 0 2
0 0 2 1
1 1 2
1 0 0
0 0 2 2
1 0 2
0 1 1 1
1 0 2
stdout
copy 
3140
1403
71
832
3140
https://ideone.com/IGJ4Vz
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!