Light Oj 1082 – Array Queries solution

1. #include<bits/stdc++.h>
2. #define mx 1000005
3. using namespace std;
4. int arr[mx];
5. int tree[mx*3];
7. void init(int node,int b,int e)
8. {
9.     if(b==e)
10.     {
11.         tree[node]=arr[b];
12.         return;
13.     }
15.     int left=node*2;
16.     int right=node*2+1;
17.     int mid=(b+e)/2;
18.     init(left,b,mid);
19.     init(right,mid+1,e);
21.     tree[node]=min(tree[left],tree[right]);
22. }
24. int query(int node,int b,int e,int i,int j)
25. {
26.     if(i>e || j<b)
27.         return mx;
28.     if(b>=i && e<=j)
29.         return tree[node];
30.     int left=node*2;
31.     int right=node*2+1;
32.     int mid=(b+e)/2;
33.     int q1=query(left,b,mid,i,j);
34.     int q2=query(right,mid+1,e,i,j);
35.     return min(q1,q2);
36. }
38. int main()
39. {
40.     int t,n,q,i,j,x,y,min;
41.     scanf(“%d”,&t);
42.     for(int i=1; i<=t; i++)
43.     {
44.         scanf(“%d %d”,&n,&q);
45.         //cin>>n>>q;
46.         for(int j=1; j<=n; j++)
47.         {
48.             //cin>>arr[j];
49.             scanf(“%d”,&arr[j]);
50.             //b[j]=a[j];
51.         }
52.         init(1,1,n);
54.         printf(“Case %d:\n”,i);
56.         for(int k=1; k<=q; k++)
57.         {
58.             //cin>>x>>y;
59.             scanf(“%d %d”,&x,&y);
60.             int ans=query(1,1,n,x,y);
61.             //cout<<ans<<endl;
62.             printf(“%d\n”,ans);
63.         }
65.     }
66.     return 0;
67. }

Light Oj 1112 – Curious Robin Hood solution

1. #include<bits/stdc++.h>

2. #define mx 100005

3. using namespace std;

4. int arr[mx];

5. int tree[mx*3];

6. void init(int node,int b,int e)

7. {

8.     if(b==e){

10.         tree[node]=arr[b];

11.         return;

12.     }

13.     int left =node*2;

14.     int right = node*2+1;

15.     int mid=(b+e)/2;

16.     init(left,b,mid);

17.     init(right,mid+1,e);

18.     tree[node]= tree[left]+tree[right];

21. }

23. int query(int node,int b,int e,int i, int j)

24. {

25.     if(b>j || e<i){

26.         return 0;

27.     }

28.     if(b>=i && e<=j){

29.         return tree[node];

30.  }

31.     int left =node*2;

32.     int right = node*2+1;

33.     int mid=(b+e)/2;

34.     int q1=query(left,b,mid,i,j);

35.     int q2=query(right,mid+1,e,i,j);

36.      return q1+q2;

37. }

39. void update(int node,int b,int e,int i,int newvalue)

40. {

43.     if(i>e || i<b)

44.         return;

45.     if(b>=i && e<=i){

46.         tree[node]=newvalue;

47.         return;

48.     }

50.     int left =node*2;

51.     int right = node*2+1;

52.     int mid=(b+e)/2;

53.     update(left,b,mid,i,newvalue);

54.     update(right,mid+1,e,i,newvalue);

55.     tree[node]= tree[left]+tree[right];

56. }

57. int main()

58. {

59.     int t,n,q,v,x,y,z;

60.     scanf("%d",&t);

61.     for(int i=1;i<=t;i++)

62.     {

63.         printf("Case %d:\n",i);

65.         scanf("%d %d",&n,&q);

66.         for(int j=0;j<n;j++){

67.             scanf("%d",&arr[j]);

68.         }

69.             init(1,0,n-1);

70.         for(int k=0;k<q;k++)

71.         {

72.             scanf("%d",&x);

73.             if(x==1)

74.             {

75.                 scanf("%d",&y);

76.                 printf("%d\n",arr[y]);

77.                 arr[y]=0;

78.                 update(1,0,n-1,y,0);

79.             }

80.             else if(x==2)

81.             {

82.                 scanf("%d %d",&y,&z);

83.                 arr[y]+=z;

84.                 update(1,0,n-1,y,arr[y]);

85.                 //printf("%d\n",ans);

86.             }

87.             else

88.             {

89.                 scanf("%d %d",&y,&z);

90.                 int ans=query(1,0,n-1,y,z);

91.                 printf("%d\n",ans);

92.             }

93.         }

94.     }

95.     return 0;

96. }

Light Oj 1164 – Horrible Queries solution

1. #include<bits/stdc++.h>
2. #define mx 100005
3. #define lld long long int
4. using namespace std;
5. lld arr[mx];
6. //lld tree[mx*3];
8. struct node{
9.         lld  prop,sum;
10. }tree[mx*3];
12. void init(lld node,lld b,lld e)
13. {
14.     if(b==e){
16.         tree[node].sum=arr[b];
17.         return;
18.     }
19.     lld left =node*2;
20.     lld right = node*2+1;
21.     lld mid=(b+e)/2;
22.     init(left,b,mid);
23.     init(right,mid+1,e);
24.     tree[node].sum= tree[left].sum+tree[right].sum;
27. }
29. lld query(lld node,lld b,lld e,lld i, lld j,lld carry=0)
30. {
31.     if(b>j || e<i){
32.         return 0;
33.     }
34.     if(b>=i && e<=j){
35.         return tree[node].sum + carry *(e-b+1);
36.  }
37.     lld left =node*2;
38.     lld right = node*2+1;
39.     lld mid=(b+e)/2;
40.     lld q1=query(left,b,mid,i,j,carry+tree[node].prop);
41.     lld q2=query(right,mid+1,e,i,j,carry+tree[node].prop);
42.      return q1+q2;
43. }
45. void update(lld node,lld b,lld e,lld i,lld j,lld x)
46. {
49.     if(b>j || e<i)
50.         return;
51.     if(b>=i && e<=j){
52.         tree[node].sum += ((e-b+1)*x);
53.         tree[node].prop += x;
54.         return;
55.     }
57.     lld left =node*2;
58.     lld right = node*2+1;
59.     lld mid=(b+e)/2;
60.     update(left,b,mid,i,j,x);
61.     update(right,mid+1,e,i,j,x);
62.     tree[node].sum= tree[left].sum+tree[right].sum+(e-b+1)*tree[node].prop;
63. }
64. int main()
65. {
66.     lld t,n,q,v,x,y,z;
67.     scanf(“%lld”,&t);
68.     for(lld i=1;i<=t;i++)
69.     {
70.         memset(arr,0,sizeof(arr));
71.         memset(tree,0,sizeof(tree));
72.         printf(“Case %d:\n”,i);
74.         scanf(“%lld %lld”,&n,&q);
76.         /*for(lld j=0;j<n;j++){
77.             scanf(“%d”,&arr[j]);
78.         }*/
79.         init(1,0,n-1);
81.         for(lld k=0;k<q;k++)
82.         {
83.             scanf(“%lld”,&x);
85.             if(x==0)
86.             {
87.                 scanf(“%lld %lld %lld”,&y,&z,&v);
88.                 //arr[y]+=z;
89.                 update(1,0,n-1,y,z,v);
90.                 //prlldf(“%d\n”,ans);
91.             }
92.             else if(x==1)
93.             {
94.                 scanf(“%lld %lld”,&y,&z);
95.                 lld ans=query(1,0,n-1,y,z,0);
96.                 printf(“%lld\n”,ans);
97.             }
98.         }
99.     }
100.     return 0;
101. }

Light Oj 1093 – Ghajini solution

1. #include<bits/stdc++.h>
2. #define mx 100005
3. using namespace std;
4. long long int arr[mx];
5. long long int max_tree[mx*3];
6. long long int min_tree[mx*3];
8. void init(long long int node,long long int b,long long int e){
9.     if(b==e)
10.         {
11.             max_tree[node]=arr[b];
12.             min_tree[node]=arr[b];
13.             return;
14.         }
15.         long long int left = node*2;
16.         long long int right = node*2+1;
17.         long long int mid=(b+e)/2;
18.         init(left,b,mid);
19.         init(right,mid+1,e);
20.         max_tree[node]=max(max_tree[left],max_tree[right]);
21.         min_tree[node]=min(min_tree[left],min_tree[right]);
24. }
27. long long int max_query(long long int node,long long int b,long long int e,long long int i,long long int j)
28. {
29.     if(e<i || b>j)
30.         return 0;
31.     if(b>=i && e<=j)
32.     {
33.         return max_tree[node];
34.     }
36.     long long int left = node*2;
37.     long long int right = node*2+1;
38.     long long int mid=(b+e)/2;
39.     long long int q1=max_query(left,b,mid,i,j);
40.     long long int q2=max_query(right,mid+1,e,i,j);
42.     return max(q1,q2);
43. }
45. long long int min_query(long long int node,long long int b,long long int e,long long int i,long long int j)
46. {
47.     if(e<i || b>j)
48.         return 10000000;
49.     if(b>=i && e<=j)
50.     {
51.         return min_tree[node];
52.     }
54.     long long int left = node*2;
55.     long long int right = node*2+1;
56.     long long int mid=(b+e)/2;
57.     long long int q1=min_query(left,b,mid,i,j);
58.     long long int q2=min_query(right,mid+1,e,i,j);
60.     return min(q1,q2);
61. }
64. int main(){
66.     long long int t,n,q,diff;
67.     scanf(“%lld”,&t);
69.     for(long long int i=1;i<=t;i++){
70.             long long int ans=0;
72.         scanf(“%lld %lld”,&n,&q);
74.         for(long long int j=1;j<=n;j++)
75.         {
76.             scanf(“%lld”,&arr[j]);
77.         }
78.         init(1,1,n);
79.         q–;
80.         for(long long int k=1;k<=n-q;k++)
81.         {
82.             long long int max1=max_query(1,1,n,k,k+q);
83.             long long int min1=min_query(1,1,n,k,k+q);
85.             long long int diff=(max1-min1);
86.             //cout<<diff<<endl;
87.             //ans=max(ans,diff);
88.             if(ans<diff)
89.                 ans=diff;
90.             //cout<<“ans “<<ans<<endl;
91.         }
92.         printf(“Case %lld: %d\n”,i,ans);
93.     }
94.     return 0;
95. }

Light Oj 1212 – Double Ended Queue solution

1. #include<bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.     int t,n,m,x,y;
6.     string s;
7.     //int a[100];
9.     cin>>t;
11.     for(int i=1; i<=t; i++)
12.     {
13.         deque<int>mydq;
14.         //memset(a,0,100);
16.         printf(“Case %d:\n”,i);
17.         cin>>n>>m;
19.         for(int j=1; j<=m; j++)
20.         {
21.             cin>>s;
22.             if(s==”pushLeft”)
23.             {
24.                 cin>>x;
25.                 if(mydq.size()==n)
26.                 {
27.                     printf(“The queue is full\n”);
28.                     //continue;
29.                 }
30.                 else
31.                 {
32.                     mydq.push_front(x);
33.                     printf(“Pushed in left: %d\n”,x);
35.                 }
36.             }
37.             else if(s==”pushRight”)
38.             {
39.                 cin>>x;
40.                 if(mydq.size()==n)
41.                 {
42.                     printf(“The queue is full\n”);
43.                     //continue;
44.                 }
45.                 else
46.                 {
47.                     mydq.push_back(x);
48.                     printf(“Pushed in right: %d\n”,x);
50.                 }
51.             }
52.             else if(s==”popLeft”)
53.             {
54.                 //cin>>x;
55.                 if(mydq.empty())
56.                 {
57.                     printf(“The queue is empty\n”);
58.                     //continue;
59.                 }
60.                 else
61.                 {
62.                     printf(“Popped from left: %d\n”,mydq.front());
63.                     mydq.pop_front();
64.                 }
65.             }
67.             else if(s==”popRight”)
68.             {
69.                 //cin>>x;
71.                 if(mydq.empty())
72.                 {
73.                     printf(“The queue is empty\n”);
74.                     //continue;
75.                 }
76.                 else
77.                 {
78.                     printf(“Popped from right: %d\n”,mydq.back());
79.                     mydq.pop_back();
80.                 }
81.             }
82.         }
83.     }
84.     return 0;
85. }

Light Oj 1080 – Binary Simulation solution

1. #include<bits/stdc++.h>
2. #define mx 100005
3. using namespace std;
4. int tree[mx*3];
7. void build_tree(int node,int b,int e)
8. {
9.     if(b==e)
10.     {
11.         tree[node]=0;
12.         return;
13.     }
14.     int left=2*node;
15.     int right=2*node+1;
16.     int mid=(b+e)/2;
18.     build_tree(left,b,mid);
19.     build_tree(right,mid+1,e);
20.     tree[node]=0;
21. }
23. void update(int node,int b,int e,int i,int j)
24. {
25.     if(j<b || i>e)
26.         return ;
27.     if(i<=b && j>=e)
28.     {
29.         tree[node]++;
30.         return ;
31.     }
33.     int left=2*node;
34.     int right=2*node+1;
35.     int mid=(b+e)/2;
37.     update(left,b,mid,i,j);
38.     update(right,mid+1,e,i,j);
41. }
44. int query(int node,int b,int e, int i)
45. {
46.     if(i<b || i > e)
47.         return 0;
48.     if(i==b && i==e)
49.         return tree[node];
51.     int left=2*node;
52.     int right=2*node+1;
53.     int mid=(b+e)/2;
55.     if(i<=mid)
56.         return tree[node]+query(left,b,mid,i);
57.     else
58.         return tree[node]+query(right,mid+1,e,i);
59. }
62. int main()
63. {
64.     int n,t,x,y,ans;
65.     char s[mx];
66.     char ch;
68.     scanf(“%d”,&n);
69.     getchar();
70.     for(int i=1; i<=n; i++)
71.     {
72.         memset(tree,0,mx*3);
73.         //cin>>s;
74.         scanf(“%s”,&s);
75.         int ln=strlen(s);
76.         //int ln=s.size();
77.         build_tree(1,1,ln);
79.         printf(“Case %d:\n”,i);
80.         scanf(“%d”,&t);
81.         getchar();
82.         for(int j=1; j<=t; j++)
83.         {
84.             scanf(“%c”,&ch);
85.             getchar();
86.             if(ch==’I’)
87.             {
88.                 scanf(“%d %d”,&x,&y);
89.                 update(1,1,ln,x,y);
90.                 getchar();
91.             }
92.             else
93.             {
94.                 scanf(“%d”,&x);
95.                 int ans=query(1,1,ln,x);
96.                 getchar();
97.                 if(ans%2==0)
98.                     printf(“%d\n”,s[x-1]-‘0’);
99.                 else
100.                     printf(“%d\n”,(s[x-1]-‘0’)^1);
101.             }
102.         }
103.     }
104.     return 0;
105. }

Light Oj 1087 – Diablo solution

1. #include<bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.     int n,t,p,q,x,y;
7.     scanf(“%d”,&t);
8.     for(int i=1;i<=t;i++)
9.     {
10.         printf(“Case %d:\n”,i);
11.         scanf(“%d %d”,&p,&q);
12.         vector<int>v;
13.         for(int j=1;j<=p;j++)
14.         {
15.             scanf(“%d”,&x);
16.             v.push_back(x);
17.         }
18.         for(int k=1;k<=q;k++)
19.         {
20.             getchar();
21.             char ch;
22.             scanf(“%c”,&ch);
23.             if(ch==’a’)
24.             {
25.                 scanf(“%d”,&y);
26.                 v.push_back(y);
27.             }
28.             else
29.             {
31.                 scanf(“%d”,&y);
32.                 if(v.size()>=y){
33.                 printf(“%d\n”,v[y-1]);
34.                 v.erase(v.begin()+y-1);
35.                 }
36.                 else
37.                     printf(“none\n”);
38.             }
39.         }
40.     }
41.     return 0;
42. }

Light oj 1088 – Points in Segments solution

1. #include<bits/stdc++.h>
2. using namespace std;
4. int points[100001];
6. int main() {
7.     int test, cs, n, i, a, b, q;
8.     scanf(“%d”, &test);
9.     for(cs = 1; cs <= test; cs++) {
10.         scanf(“%d %d”, &n, &q);
11.         for(i = 0; i < n; i++) scanf(“%d”, points + i);
12.         printf(“Case %d:\n”, cs);
13.         while(q–) {
14.             scanf(“%d %d”, &a, &b);
15.             a = lower_bound(points, points + n, a) – points;
16.             b = upper_bound(points + a, points + n, b) – points;
17.             printf(“%d\n”, b – a);
18.         }
19.     }
20.     return 0;
21. }

Uva 11597 solution

#include<bits/stdc++.h>
using namespace std;
int main()
{

int n,m=0;
while(cin>>n)
{
if(n==0)
break;
else
{
m++;
cout<<“Case “<<m<<“: “<<n/2<<endl;
}
}
return 0;
}

WelCome To My world

আমি মোঃ ইকবাল হোসেন ইকরা,জন্ম ১৯৯৪ ,২৪ অক্টোবর ।স্কুল ও কলেজ দুটোই রাজেন্দ্রপুর ক্যান্টনমেন্ট পাবলিক স্কুল ও কলেজ ।২০১০ এ এস,এস,সি আর ২০১২ তে এইচ,এস,সি পাশ করি । বর্তমানে আমি মাওলান ভাসানি বিজ্ঞান ও প্রযুক্তি বিশ্ববিদ্যালয় এ আই,সি,টি বিভাগে আধ্যায়ণ করছি । জন্ম মাদারিপুরের কালকিনি থানার উত্তর রমজান পুর গ্রামে । বর্তমানে গাজীপুরের রাজেন্দ্রপুর ক্যান্টনমেন্ট এ আছি ।