fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<climits>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<stdlib.h>
  7. #include<algorithm>
  8. #define getcx getchar_unlocked
  9. #ifndef ONLINE_JUDGE
  10.     #define getcx getchar
  11. #endif
  12. using namespace std;
  13. #define ull unsigned long long
  14. #define lli long long int
  15. #define li long int
  16. #define ii int
  17. #define mod 1000000007
  18. /* Created by : Rahul Johari
  19. 				Thapar University */
  20.  
  21. inline int inp()
  22. {
  23.    int n=0;
  24.    int ch=getcx();int sign=1;
  25.    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
  26.  
  27.    while(  ch >= '0' && ch <= '9' )
  28.            n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
  29.    return n*sign;
  30. }
  31. inline long long in()
  32. {
  33.    long long n=0;
  34.    long long ch=getcx();long long sign=1;
  35.    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
  36.  
  37.    while(  ch >= '0' && ch <= '9' )
  38.            n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
  39.    return n*sign;
  40. }
  41.  
  42. lli getMid(lli s, lli e) {  return s + (e -s)/2;  }
  43.  
  44. lli getSumUtil(lli *st, lli ss, lli se, lli qs, lli qe, lli index)
  45. {
  46.     if (qs <= ss && qe >= se)
  47.         return st[index];
  48.  
  49.     if (se < qs || ss > qe)
  50.         return 0;
  51.  
  52.     lli mid = getMid(ss, se);
  53.     return getSumUtil(st, ss, mid, qs, qe, 2*index+1) +
  54.            getSumUtil(st, mid+1, se, qs, qe, 2*index+2);
  55. }
  56.  
  57. void updateValueUtil(lli *st, lli ss, lli se, lli i, lli diff, lli index)
  58. {
  59.     if (i < ss || i > se)
  60.         return;
  61.  
  62.     st[index] = st[index] + diff;
  63.     if (se != ss)
  64.     {
  65.         lli mid = getMid(ss, se);
  66.         updateValueUtil(st, ss, mid, i, diff, 2*index + 1);
  67.         updateValueUtil(st, mid+1, se, i, diff, 2*index + 2);
  68.     }
  69. }
  70.  
  71. void updateValue(lli arr[], lli *st, lli n, lli i, lli new_val)
  72. {
  73.     if (i < 0 || i > n-1)
  74.     {
  75.         printf("Invalid Input");
  76.         return;
  77.     }
  78.  
  79.     lli diff = new_val - arr[i];
  80.  
  81.     arr[i] = new_val;
  82.  
  83.     updateValueUtil(st, 0, n-1, i, diff, 0);
  84. }
  85.  
  86. lli getSum(lli *st, lli n, lli qs, lli qe)
  87. {
  88.     if (qs < 0 || qe > n-1 || qs > qe)
  89.     {
  90.         printf("Invalid Input");
  91.         return -1;
  92.     }
  93.  
  94.     return getSumUtil(st, 0, n-1, qs, qe, 0);
  95. }
  96.  
  97. lli constructSTUtil(lli arr[], lli ss, lli se, lli *st, lli si)
  98. {
  99.     if (ss == se)
  100.     {
  101.         st[si] = arr[ss];
  102.         return arr[ss];
  103.     }
  104.  
  105.     lli mid = getMid(ss, se);
  106.     st[si] =  constructSTUtil(arr, ss, mid, st, si*2+1) +
  107.               constructSTUtil(arr, mid+1, se, st, si*2+2);
  108.     return st[si];
  109. }
  110.  
  111. /* inline lli power_of_2_mod(lli n) {
  112.     lli result = 1;
  113.     if (n <= 63) {
  114.         result <<= n;
  115.         result = result % 1000000007;
  116.     }
  117.     else {
  118.         lli one = 1;
  119.         one <<= 63;
  120.         while (n > 63) {
  121.             result = ((result % 1000000007) * (one % 1000000007)) % 1000000007;
  122.             n -= 63;
  123.         }
  124.  
  125.         for (lli i = 1; i <= n; ++i) {
  126.             result = (result * 2) % 1000000007;
  127.         }
  128.  
  129.     }
  130.  
  131.     return result;
  132. } */
  133.  
  134. lli *constructST(lli arr[], lli n)
  135. {
  136.     lli x = (lli)(ceil(log2(n)));
  137.     lli max_size = 2*(1<<x) - 1;
  138.     lli *st = new lli[max_size];
  139.  
  140.     constructSTUtil(arr, 0, n-1, st, 0);
  141.  
  142.     return st;
  143. }
  144.  
  145. int main()
  146. {
  147.  
  148.     lli x,y,n,M,total,i,j,max,d;
  149.     char O;
  150.     bool flag;
  151.  
  152.     n = in();
  153.     M = in();
  154.  
  155.     lli arr[n+1];
  156.     for ( i=0;i<n;i++ )
  157.     arr[i] = in();
  158.  
  159.     // Build segment tree from given array
  160.     lli *st = constructST(arr, n);
  161.     while ( M-- )
  162.     {
  163.     	flag = true;
  164.  
  165.     	cin >> O;
  166.     	if ( O == 'S' )
  167.     	{
  168.     		x = in();
  169.     		y = in();
  170.     		x -= 1;
  171.     		y -= 1;
  172.     		printf("%lld\n",getSum(st,n,x,y));
  173.     	}
  174.     	max = INT_MIN;
  175.     	if ( O == 'M')
  176.     	{
  177.     		x = in();
  178.     		y = in();
  179.     		x -= 1;
  180.     		y -= 1;
  181.  
  182.     		for ( i=x;i<=y;i++ )
  183.     		{
  184.     			if ( arr[i] > max )
  185.     			max = arr[i];
  186.     		}
  187.     		printf("%lld\n", max );
  188.     	}
  189.  
  190.     	if ( O == 'U' )
  191.     	{
  192.     		x = in();
  193.     		d = in();
  194.     		x -= 1;
  195.  
  196.     		updateValue(arr, st, n, x, d);
  197.     	}
  198.  
  199.     	if ( O == 'I' )
  200.     	{
  201.     		x = in();
  202.     		y = in();
  203.     		x -= 1;
  204.     		y -= 1;
  205.  
  206.     		for ( i=x;i<=y;i++ )
  207.     		{
  208.     			if ( (arr[i]<arr[i+1]) && flag )
  209.     			continue;
  210.     			else
  211.     			{
  212.     				flag = false;
  213.     				break;
  214.     			}
  215.     		}
  216.  
  217.     		if ( flag == true )
  218.     		printf("1\n");
  219.     		else
  220.     		printf("0\n");
  221.     	}
  222.  
  223.     	if ( O == 'D' )
  224.     	{
  225.     		x = in();
  226.     		y = in();
  227.     		x -= 1;
  228.     		y -= 1;
  229.  
  230.     		for ( i=x;i<=y;i++ )
  231.     		{
  232.     			if ( (arr[i]>arr[i+1]) && flag )
  233.     			continue;
  234.     			else
  235.     			{
  236.     				flag = false;
  237.     				break;
  238.     			}
  239.     		}
  240.  
  241.     		if ( flag == true )
  242.     		printf("1\n");
  243.     		else
  244.     		printf("0\n");
  245.     	}
  246.     }
  247.     return 0;
  248. }
Success #stdin #stdout 0s 2832KB
comments (?)
stdin
copy 
5 7
1 2 4 5 10
S 1 5
S 1 4
M 1 5
I 2 4
U 2 11
M 1 5
D 3 4
stdout
copy 
22
12
10
1
11
0
https://ideone.com/5GnsNa
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

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!