- #include <bits/stdc++.h>
- using namespace std;
- #define llu long long unsigned
- llu c[2][2];
- //llu MOD=11221212121121;
- llu p, q,n;
- void mul(llu a[2][2],llu b[2][2]){
- memset(c, 0, sizeof(c));
- for(int i = 0; i <2; i++){
- for(int j = 0; j <2; j++){
- for(int k = 0; k <2; k++){
- c[i][j]+= ((a[i][k])*(b[k][j]));
- //c[j][j]%=MOD;
- }
- }
- }
- for(int i = 0; i <2; i++){
- for(int j = 0; j <2; j++){
- a[i][j] = c[i][j];
- }
- }
- }
- void ans(llu a[2][2], llu n){
- llu m[2][2] = {{p, -q}, {1,0}};
- if(n == 1) return;
- ans(a, n/2);
- mul(a, a);
- if(n%2) mul(a, m);
- }
- int main(){
- int ts;
- scanf("%d", &ts);
- for(int s = 1; s <= ts; s++){
- llu answer;
- scanf("%llu%llu%llu",&p, &q, &n);
- llu f[2][2] = {{p, -q}, {1,0}};
- //llu f1 = p%MOD;
- //llu f2 = ((p%MOD)*(p%MOD))%MOD-(2*q)%MOD;
- if(n<1) answer = 2;
- else if(n == 1) answer = p;
- //else if(n == 2) answer = f2;
- else if(n>1) ans(f, n-1), answer = (p*f[0][0]+2*f[0][1]);
- printf("Case %d: %llu\n", s,answer);
- }
- return 0;
- }
Saturday 29 July 2017
Lightoj 1070 - Algebraic Problem
Lightoj 1093 - Ghajini
- #include <bits/stdc++.h>
- using namespace std;
- #define mx 100001
- int arr[mx];
- int tree[mx * 3];
- int tree1[mx*3];
- void init(int node, int b, int e)
- {
- if (b == e) {
- tree[node] = arr[b];
- return;
- }
- int Left = node * 2;
- int Right = node * 2 + 1;
- int mid = (b + e) / 2;
- init(Left, b, mid);
- init(Right, mid + 1, e);
- tree[node] = min(tree[Left], tree[Right]);
- }
- int query(int node, int b, int e, int i, int j)
- {
- if (i > e || j < b)
- return INT_MAX; //বাইরে চলে গিয়েছে
- if (b >= i && e <= j)
- return tree[node]; //রিলেভেন্ট সেগমেন্ট
- int Left = node * 2; //আরো ভাঙতে হবে
- int Right = node * 2 + 1;
- int mid = (b + e) / 2;
- int p1 = query(Left, b, mid, i, j);
- int p2 = query(Right, mid + 1, e, i, j);
- return min(p1, p2); //বাম এবং ডান পাশের যোগফল
- }
- void init1(int node, int b, int e)
- {
- if (b == e) {
- tree1[node] = arr[b];
- return;
- }
- int Left = node * 2;
- int Right = node * 2 + 1;
- int mid = (b + e) / 2;
- init1(Left, b, mid);
- init1(Right, mid + 1, e);
- tree1[node] = max(tree1[Left], tree1[Right]);
- }
- int query1(int node, int b, int e, int i, int j)
- {
- if (i > e || j < b)
- return INT_MIN; //বাইরে চলে গিয়েছে
- if (b >= i && e <= j)
- return tree1[node]; //রিলেভেন্ট সেগমেন্ট
- int Left = node * 2; //আরো ভাঙতে হবে
- int Right = node * 2 + 1;
- int mid = (b + e) / 2;
- int p1 = query1(Left, b, mid, i, j);
- int p2 = query1(Right, mid + 1, e, i, j);
- return max(p1,p2); //বাম এবং ডান পাশের যোগফল
- }
- int main()
- {
- int ts;
- scanf("%d", &ts);
- for(int p = 1; p <=ts; p++){
- int n, d;
- scanf("%d%d", &n, &d);
- for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);
- init(1, 1, n);
- init1(1, 1, n);
- int l, r;
- int ans = 0;
- for(int j = 1; j <=n-d+1; j++){
- int s = query(1, 1, n, j, j+d-1);
- int r = query1(1, 1, n, j, j+d-1);
- //cout<<j<<" = j j+d-1 = "<<j+d-1<<" s = "<<s<<" r = "<<r<<endl;
- if(s != INT_MAX && r != INT_MIN) ans = max(ans, r-s);
- }
- printf("Case %d: %d\n", p, ans);
- }
- return 0;
- }
Lightoj 1080 - Binary Simulation
- #include <bits/stdc++.h>
- using namespace std;
- #define mx 100005
- int a[mx];
- int n;
- int update(int indx, int v){
- while(indx<=n){
- a[indx]+=v;
- indx+= (indx&(-indx));
- }
- }
- int query(int indx){
- int sum = 0;
- while(indx>0){
- sum+= a[indx];
- indx-=(indx&(-indx));
- }
- return sum;
- }
- int main()
- {
- int ts;
- scanf("%d", &ts);
- for(int p = 1; p <=ts; p++){
- memset(a, 0, sizeof(a));
- printf("Case %d:\n", p);
- char s[mx];
- scanf("%s", s);
- int q;
- n = strlen(s);
- scanf("%d", &q);
- for(int i = 0; i<q ; i++){
- char ch;
- int l, r, p;
- getchar();
- scanf("%c", &ch);
- if(ch=='I'){
- scanf("%d%d", &l, &r);
- update(l, 1);
- update(r+1, -1);
- }
- else if(ch == 'Q'){
- scanf("%d", &p);
- int a = (query(p)%2);
- if(a == 0) printf("%c\n", s[p-1]);
- else {
- if(s[p-1] == '0') printf("1\n");
- else printf("0\n");
- }
- }
- }
- }
- return 0;
- }
Lightoj 1164 - Horrible Queries
- #include <bits/stdc++.h>
- using namespace std;
- #define mx 100001
- int arr[mx];
- #define ll long long unsigned
- struct info {
- ll prop, sum;
- } tree[mx * 3];
- void init(int node, int b, int e)
- {
- if (b == e) {
- tree[node].sum = arr[b];
- tree[node].prop = 0;
- return;
- }
- int Left = node * 2;
- int Right = node * 2 + 1;
- int mid = (b + e) / 2;
- init(Left, b, mid);
- init(Right, mid + 1, e);
- tree[node].sum = (tree[Left].sum+ tree[Right].sum);
- tree[node].prop = 0;
- }
- ll query(int node, int b, int e, int i, int j, ll carry = 0)
- {
- if (i > e || j < b)
- return 0;
- if (b >= i and e <= j)
- return tree[node].sum + carry * (e - b + 1); //সাম এর সাথে যোগ হবে সেই রেঞ্জের সাথে অতিরিক্ত যত যোগ করতে বলেছে সেটা
- int Left = node << 1;
- int Right = (node << 1) + 1;
- int mid = (b + e) >> 1;
- ll p1 = query(Left, b, mid, i, j, carry + tree[node].prop); //প্রপাগেট ভ্যালু বয়ে নিয়ে যাচ্ছে carry ভ্যারিয়েবল
- ll p2 = query(Right, mid + 1, e, i, j, carry + tree[node].prop);
- return p1 + p2;
- }
- void update(int node, int b, int e, int i, int j, ll x)
- {
- if (i > e || j < b)
- return;
- if (b >= i && e <= j) //নোডের রেঞ্জ আপডেটের রেঞ্জের ভিতরে
- {
- tree[node].sum += ((e - b + 1) * x); //নিচে নোড আছে e-b+1 টি, তাই e-b+1 বার x যোগ হবে এই রেঞ্জে
- tree[node].prop += x; //নিচের নোডগুলোর সাথে x যোগ হবে
- return;
- }
- int Left = node * 2;
- int Right = (node * 2) + 1;
- int mid = (b + e) / 2;
- update(Left, b, mid, i, j, x);
- update(Right, mid + 1, e, i, j, x);
- tree[node].sum = tree[Left].sum + tree[Right].sum + (e - b + 1) * tree[node].prop;
- //উপরে উঠার সময় পথের নোডগুলো আপডেট হবে
- //বাম আর ডান পাশের সাম ছাড়াও যোগ হবে নিচে অতিরিক্ত যোগ হওয়া মান
- }
- int main()
- {
- int ts;
- scanf("%d", &ts);
- for(int p = 1; p <=ts; p++){
- memset(arr, 0, sizeof(arr));
- memset(tree, 0, sizeof(tree));
- printf("Case %d:\n", p);
- int n, q;
- scanf("%d%d", &n, &q);
- //for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);
- //init(1, 1, n);
- for(int i = 0; i<q ; i++){
- int num;
- scanf("%d", &num);
- if(num == 0){
- int x, y, v;
- scanf("%d%d%d", &x, &y, &v);
- update(1, 1, n, x+1, y+1, v);
- }
- else if(num == 1){
- int x, y;
- scanf("%d%d", &x, &y);
- printf("%lld\n", query(1, 1, n, x+1, y+1, 0));
- }
- }
- }
- return 0;
- }
Subscribe to:
Posts (Atom)
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...
-
Problem link: Problem Analysis: It is actually a basic Bisection problem , as we can see here we can not actually find a formula fo...
-
http://lightoj.com/volume_showproblem.php?problem=1382 Problem analysis: This is a rare problem i wrote about so far. After much strugg...