Lightoj 1112 - Curious Robin Hood

http://lightoj.com/volume_showproblem.php?problem=1112

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100001
4. int arr[mx];
5. int tree[mx * 3];
6. void init(int node, int b, int e)
7. {
8.     if (b == e) {
9.         tree[node] = arr[b];
10.         return;
11.     }
12.     int Left = node * 2;
13.     int Right = node * 2 + 1;
14.     int mid = (b + e) / 2;
15.     init(Left, b, mid);
16.     init(Right, mid + 1, e);
17.     tree[node] = (tree[Left]+ tree[Right]);
18. }
19. int query(int node, int b, int e, int i, int j)
20. {
21.     if (i > e || j < b)
22.         return 0; //বাইরে চলে গিয়েছে
23.     if (b >= i && e <= j)
24.         return tree[node]; //রিলেভেন্ট সেগমেন্ট
25.     int Left = node * 2; //আরো ভাঙতে হবে
26.     int Right = node * 2 + 1;
27.     int mid = (b + e) / 2;
28.     int p1 = query(Left, b, mid, i, j);
29.     int p2 = query(Right, mid + 1, e, i, j);
30.     return (p1+p2); //বাম এবং ডান পাশের যোগফল
31. }
32.  
33. void update(int node, int b, int e, int i, int newvalue)
34. {
35.     if (i > e || i < b)
36.         return; //বাইরে চলে গিয়েছে
37.     if (b >= i && e <= i) { //রিলেভেন্ট সেগমেন্ট
38.         tree[node] = newvalue; //নতুন মান বসিয়ে দিলাম
39.         return;
40.     }
41.     int Left = node * 2; //আরো ভাঙতে হবে
42.     int Right = node * 2 + 1;
43.     int mid = (b + e) / 2;
44.     update(Left, b, mid, i, newvalue);
45.     update(Right, mid + 1, e, i, newvalue);
46.     tree[node] = tree[Left] + tree[Right];
47. }
48.  
49. int main()
50. {
51.     int ts;
52.     scanf("%d", &ts);
53.     for(int p = 1; p <=ts; p++){
54.     printf("Case %d:\n", p);
55.     int n, q;
56.     scanf("%d%d", &n, &q);
57.     for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);  
58.         init(1, 1, n);
59.         for(int i = 0; i<q ; i++){
60.         int a;
61.         scanf("%d", &a);
62.         if(a == 1){
63.             int p;
64.             scanf("%d", &p);
65.             printf("%d\n",query(1, 1, n, p+1, p+1));
66.             update(1, 1, n, p+1, 0);
67.         }
68.         else if(a == 2){
69.             int p, v;
70.             scanf("%d%d", &p, &v);
71.             update(1, 1, n, p+1, query(1, 1, n, p+1, p+1)+v);
72.         }
73.         else if(a == 3){
74.             int c, b;
75.             scanf("%d%d", &c, &b);
76.             printf("%d\n",query(1, 1, n, c+1, b+1));   
77.         }
78.         //for(int i = 1; i <=n; i++) cout<<arr[i]<<" ";
79.         //cout<<endl;
80.     }
81.     }
82.     return 0;
83. }

Lightoj 1245 - Harmonic Number (II)

http://lightoj.com/volume_showproblem.php?problem=1245

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. int main(){
5.     int ts;
6.     scanf("%d", &ts);
7.     for(int p = 1; p <= ts; p++){
8.     int n;
9.     scanf("%d", &n);
10.     llu sum = 0;
11.     int m = sqrt(n);
12.     for(int i = 1; i<= m; i++) sum += (n/i);
13.     for(int i = 1; i<= m; i++){
14.         sum+= ((n/i)-(n/(i+1)))*i;
15.     }
16.     if(m==n/m) sum -= m;
17.     printf("Case %d: %llu\n",p,  sum);
18.     }
19.     return 0;
20. }

Lightoj 1082 - Array Queries

http://lightoj.com/volume_showproblem.php?problem=1082

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100001
4. int arr[mx];
5. int tree[mx * 3];
6. void init(int node, int b, int e)
7. {
8.     if (b == e) {
9.         tree[node] = arr[b];
10.         return;
11.     }
12.     int Left = node * 2;
13.     int Right = node * 2 + 1;
14.     int mid = (b + e) / 2;
15.     init(Left, b, mid);
16.     init(Right, mid + 1, e);
17.     tree[node] = min(tree[Left], tree[Right]);
18. }
19. int query(int node, int b, int e, int i, int j)
20. {
21.     if (i > e || j < b)
22.         return INT_MAX; //বাইরে চলে গিয়েছে
23.     if (b >= i && e <= j)
24.         return tree[node]; //রিলেভেন্ট সেগমেন্ট
25.     int Left = node * 2; //আরো ভাঙতে হবে
26.     int Right = node * 2 + 1;
27.     int mid = (b + e) / 2;
28.     int p1 = query(Left, b, mid, i, j);
29.     int p2 = query(Right, mid + 1, e, i, j);
30.     return min(p1,p2); //বাম এবং ডান পাশের যোগফল
31. }
32.  
33. int main()
34. {
35.     int ts;
36.     scanf("%d", &ts);
37.     for(int p = 1; p <=ts; p++){
38.     printf("Case %d:\n", p);
39.     int n, q;
40.     scanf("%d%d", &n, &q);
41.     for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);  
42.     init(1, 1, n);
43.     for(int i = 0;i <q; i++){
44.         int a, b;
45.         scanf("%d%d", &a, &b);
46.         printf("%d\n",query(1, 1, n, a, b));
47.     }
48.     }
49.     return 0;
50. }

Lightoj 1213 - Fantasy of a Summation

http://lightoj.com/volume_showproblem.php?problem=1213

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. long long mod_pow(long long b, long long e, long long m) {
5.   long long ans = 1;
6.   while (e > 0) {
7.     if (e & 1)
8.       ans = (ans * b) % m;
9.     b = (b * b) % m;
10.     e >>= 1;
11.   }
12.   return ans;
13. }
14.  
15. int main(){
16.     int ts;
17.     scanf("%d", &ts);
18.     for(int p = 1; p <= ts; p++){
19.     llu sum = 0, n, k, m;
20.     scanf("%llu%llu%llu",&n, &k, &m);
21.     for(llu i =0; i <n; i++){
22.         llu a;
23.         scanf("%llu", &a);
24.         sum+= a;
25.     }
26.     llu ans = k;
27.     ans = (ans*(mod_pow(n, k-1, m)))%m;
28.     //cout<<"ans = "<<sum<<endl;
29.     ans = (ans*sum)%m;
30.     printf("Case %d: %llu\n",p, ans);
31.     }
32.     return 0;
33. }

Lightoj 1338 - Hidden Secret!

http://lightoj.com/volume_showproblem.php?problem=1338

1. 
   
2. 
   
3. 
   
4. 
   
5. #include <stdio.h>
6. #include <string.h>
7. 
   
8. int main()
9. {
10.     int tst, i, j, cndtn;
11.     char a[120], b[120];
12.     scanf("%d", &tst);
13.     getchar();
14.     for(i=1; i<=tst; i++)
15.     {
16.         int a1[26], b1[26];
17.         for(j=0; j<26; j++)
18.         {
19.             a1[j] = 0; b1[j] = 0;
20.         }
21.         gets(a);
22.         gets(b);
23.         for(j=0; a[j]; j++)
24.         {
25.             if(a[j]>=65 && a[j]<=90)
26.                 a1[a[j]-65]++;
27.             else if(a[j]>=97 && a[j]<=122)
28.                 a1[a[j]-97]++;
29.         }
30.         for(j=0; b[j]; j++)
31.         {
32.             if(b[j]>=65 && b[j]<=90)
33.                 b1[b[j]-65]++;
34.             else if(b[j]>=97 && b[j]<=122)
35.                 b1[b[j]-97]++;
36.         }
37.         for(j=0, cndtn=1; j<26; j++)
38.         {
39.             if(a1[j]!=b1[j])
40.             {
41.                 printf("Case %d: No\n", i);
42.                 cndtn = 0;
43.                 break;
44.             }
45.         }
46.         if(cndtn==1) printf("Case %d: Yes\n", i);
47.  
48.     }
49.     return 0;
50. }