Saturday 29 July 2017

Lightoj 1070 - Algebraic Problem

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define llu long long unsigned
  4. llu c[2][2];
  5. //llu MOD=11221212121121;
  6. llu p, q,n;
  7. void mul(llu a[2][2],llu b[2][2]){
  8.     memset(c, 0sizeof(c));
  9.     for(int i = 0; i <2; i++){
  10.         for(int j = 0; j <2; j++){
  11.             for(int k = 0; k <2; k++){
  12.                 c[i][j]+= ((a[i][k])*(b[k][j]));
  13.                 //c[j][j]%=MOD;
  14.             }
  15.         }
  16.     }
  17.     for(int i = 0; i <2; i++){
  18.         for(int j = 0; j <2; j++){
  19.             a[i][j] = c[i][j];
  20.         }
  21.     }
  22. }
  23. void ans(llu a[2][2], llu n){
  24.     llu m[2][2] = {{p, -q}{1,0}};
  25.     if(== 1) return;
  26.     ans(a, n/2);
  27.     mul(a, a);
  28.     if(n%2) mul(a, m);
  29. }
  30. int main(){
  31.     int ts;
  32.     scanf("%d"&ts);
  33.     for(int s = 1; s <= ts; s++){
  34.     llu answer;
  35.     scanf("%llu%llu%llu",&p, &q, &n);
  36.     llu f[2][2] = {{p, -q}{1,0}};
  37.     //llu f1 = p%MOD;
  38.     //llu f2 = ((p%MOD)*(p%MOD))%MOD-(2*q)%MOD;
  39.     if(n<1) answer = 2;
  40.     else if(== 1) answer = p;
  41.     //else if(n == 2) answer  = f2;
  42.     else if(n>1) ans(f, n-1), answer = (p*f[0][0]+2*f[0][1]);
  43.     printf("Case %d: %llu\n", s,answer);
  44.     }
  45.     return 0;
  46. }

Lightoj 1093 - Ghajini

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

Lightoj 1080 - Binary Simulation

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mx 100005
  4. int a[mx];
  5. int n;
  6. int update(int indx, int v){
  7.     while(indx<=n){
  8.         a[indx]+=v;
  9.         indx+= (indx&(-indx));
  10.     }
  11. }
  12. int query(int indx){
  13.     int sum = 0;
  14.     while(indx>0){
  15.         sum+= a[indx];
  16.         indx-=(indx&(-indx));
  17.     }
  18.     return sum;
  19. }
  20. int main()
  21. {
  22.     int ts;
  23.     scanf("%d"&ts);
  24.     for(int p = 1; p <=ts; p++){
  25.     memset(a, 0sizeof(a));
  26.     printf("Case %d:\n", p);
  27.     char s[mx];
  28.     scanf("%s", s);
  29.     int q;
  30.     n = strlen(s);
  31.     scanf("%d"&q);
  32.         for(int i = 0; i<; i++){
  33.         char ch;
  34.         int l, r, p;
  35.         getchar();
  36.         scanf("%c"&ch);
  37.         if(ch=='I'){
  38.             scanf("%d%d"&l, &r);
  39.             update(l, 1);
  40.             update(r+1-1);
  41.         }
  42.         else if(ch == 'Q'){
  43.             scanf("%d"&p);
  44.             int a = (query(p)%2);
  45.             if(== 0) printf("%c\n", s[p-1]);
  46.             else {
  47.                 if(s[p-1] == '0') printf("1\n");
  48.                 else printf("0\n");
  49.             }
  50.         }
  51.        
  52.     }
  53.     }
  54.     return 0;
  55. }

Lightoj 1164 - Horrible Queries

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

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...