**Swap Pairing( minimum number of steps in which we can make all number pair together)

Swap Pairing

You are given an array of N values. It is guaranteed that N is even and that each distinct value appears in the array exactly twice.

On this array, you can perform the following operation: choose two adjacent numbers and swap them. Compute the minimum number of operations needed such that each pair of equal numbers will be adjacent.

Standard input

The first line contains a single integer N, the length of the array.

The second line contains the N values of the array.

Standard output

The output should contain a single integer representing the minimum number of operations needed.

Constraints and notes

• 1 ≤ N ≤ 100 000
• The values of the array are between 0 and 109

Task Limits

• Time limit: 500 ms
• Memory limit: 128 MB

Input	Output	Explanation
8 7 3 5 3 7 6 5 6	5	The swaps are as follows: 7 3 5 3 7 6 5 6 7 3 5 7 3 6 5 6 7 3 7 5 3 6 5 6 7 7 3 5 3 6 5 6 7 7 3 3 5 6 5 6 7 7 3 3 5 5 6 6

--------------------------------------------------editorial-------------------------------------------------

first observation in this problem is that for any pair   we can shift any one towards any other , it will always give optimal answer ,,,

start from the first element if we  get  any number whose  first pair not used till now than just  map  its position in the array ,

else if we get any number whose first number  is already used , than add index diff of last  occurance and this number  and increase index of all numbers lies b/w these numbers , 9 since we are shifting second number toward first one soo all numbers in b/w these pair shift by 1 index ) 

we can easily do this update , and query using seg tree, 

but use of BIT in such problem will work fast .....

----------------------------------------------code-----seg tree----------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int arr[1000000];

int val[1000000];

int seg[10000000];

int lazy[10000000];

void build( int idx,int start,int end)

 {

 

  if(start>end) return ;

  else if(start==end)

   {

    seg[idx]=val[start];

    return ;

  }

  build(2*idx,start,(start+end)/2);

  build(2*idx+1,(start+end)/2+1,end);

 }

void update(int idx,int start,int end,int ups,int upe,int val)

 {

  if(start>end || end<ups || upe<start) return ;

  else if(lazy[idx])

    {

       seg[idx]+= lazy[idx];

       if(start!=end)

       {

        lazy[2*idx]+=lazy[idx];

        lazy[2*idx+1]=lazy[idx];

  }

  lazy[idx]=0;

  }

  

  if(start>=ups && end<= upe)

   {

     seg[idx]+=val;

     if(start!=end)

      {

      lazy[2*idx]+=val;

      lazy[2*idx+1]+=val;

  }

  return ;

}

update(2*idx,(start),(start+end)/2,ups,upe,val);

update(2*idx+1,(start+end)/2+1,end,ups,upe,val);

 }

 int query(int idx,int start,int end,int qs,int qe)

  {

   

   

   if(lazy[idx])

    {

       seg[idx]+= lazy[idx];

       if(start!=end)

       {

        lazy[2*idx]+=lazy[idx];

        lazy[2*idx+1]=lazy[idx];

  }

  lazy[idx]=0;

  }

 

  if(start>end || end<qs || qe<start) return 0;

  

  if(start==end)

   {

     return  seg[idx];

}

int a=query(2*idx,start,(start+end)/2,qs,qe);

int b=query(2*idx+1,(start+end)/2+1,end,qs,qe);

return (a+b);

  

  }

  map<int,int> ma;

int main()

{

int  n;

cin>>n;

 

for(int i=1;i<=n;i++) cin>>arr[i];

 

for(int i=0;i<=n;i++) val[i]=i;

 

build(1,1,n);

lli ans=0;

for(int i=1;i<=n;i++)

 {

  if(ma[arr[i]]==0) ma[arr[i]]=i;

  else

    {

   //  cout<<" i "<<i<<" "<<arr[i]<<endl;

      int last=ma[arr[i]];

   //   cout<<"last is "<<last<<endl;

  int id=query(1,1,n,last,last);

  ans+=i-id-1;

 // cout<<"ns "<<ans<<endl;

  update(1,1,n,id,i,1);

  }

 }

 

cout<<ans<<endl;

}

--------------------------------code--------------------bit-------------------------------------------------

#include<bits/stdc++.h> using namespace std; #define ll long long int ll BIT[100010]; int n; void update (int idx,int val) { while( idx <= n) { BIT[idx] += val ; idx += (idx&-idx) ; } } ll query (int idx) { ll ans = 0 ; while (idx > 0 ) { ans += BIT[idx] ; idx -= (idx&-idx) ; } return ans ; } void rupdate(int i, int j, int v) { update(i, v); update(j + 1, -v); } int a[100010]; map<int,int> lt,rt; int main() { // rupdate(4,6,1); //int q=query(6); // cout<<q<<endl; // int n; cin>>n; ll ans=0; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { rt[a[i]]=i; } for(int i=n;i>=1;i--) { lt[a[i]]=i; } //cout<<"here "<<endl; for(int i=1;i<=n;i++) { int val=lt[a[i]]; //cout<<"here "<<endl; if(i>val) { // cout<<"insie at "<<i<<" "<<endl; int q=query(val); // cout<<"q "<<q<<endl; int l=val+q; // cout<<"cirtual left "<<l<<endl; int r=rt[a[i]]; ll temp=(r-l)-1; ans+=temp; // cout<<"tmep ans "<<temp<<endl; // cout<<"upd iwth "<<val+1<<" "<<r-1<<endl; rupdate(val+1,r-1,1); // cout<<"range upd done "<<endl; } } cout<<ans<<endl; return 0; }

**1085 - All Possible Increasing Subsequences

                                1085 - All Possible Increasing Subsequences


An increasing subsequence from a sequence A1, A2 ... An is defined by Ai1, Ai2 ... Aik, where the following properties hold

1.      i1 < i2 < i3 < ... < ik and
2.      Ai1 < Ai2 < Ai3 < ... < Aik

Now you are given a sequence, you have to find the number of all possible increasing subsequences.

Input
Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 105) denoting the number of elements in the initial sequence. The next line will contain n integers separated by spaces, denoting the elements of the sequence. Each of these integers will be fit into a 32 bit signed integer.

Output
For each case of input, print the case number and the number of possible increasing subsequences modulo 1000000007.

Sample Input
Output for Sample Input
3
3
1 1 2
5
1 2 1000 1000 1001
3
1 10 11
Case 1: 5
Case 2: 23
Case 3: 7
Notes
1.      For the first case, the increasing subsequences are (1), (1, 2), (1), (1, 2), 2.
2.      Dataset is huge, use faster I/O methods.

----------------------------------------EDITORIAL---------------------------------------------------------------
THIS PROBLEM CAN BE EASILY SOLVED  USING SEG TREE ,  FIRST OF ALL SORT ALL THE ELEMENTS WITH THERE INDEX , SINCE ANY NUMBER  CAN BE PLACED AFTER ANY NUMBER LESS THAN THAT NUMBER AND COMES BEFORE THAT NUMBER.....

AFTER SORTING  NOW WE PROCESS EACH ELEMENT ONE BY ONE , AND  FOR ANY NUMBER IT CAN BE PLACED  AFTER ALL NUMBER PROCESSED TILL NOW AND HAVE INDEX LESS THAN INDEX OF THIS NUMBER ,
SO BASICALLY WE CAN PLACE THIS NUMBER AFTER ALL POSSIBLE SEQUENCE TILL IDX-1 ,
SO IT IS THE SUM FROM  0 TO IDX-1,

AND ALSO UPDATE THIS SUM AT IDX

-----------------------------------------------CODE------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef  int lli;
vector<pair<lli,int> > v;
lli arr[1000000];
lli seg[1000000];

#define mod 1000000007
void  update(int idx,int start,int end,int ups,int upe,int val)
 {
  if(start>end  ||upe<start || ups>end)
   {
    return ;
  }
  else if(start==end  && start==ups)
   {
    seg[idx]=(seg[idx]+val)%mod;
    return ;
}
int mid=(start+end)/2;
update(2*idx,start,mid,ups,upe,val);
update(2*idx+1,mid+1,end,ups ,upe,val);
seg[idx]=(seg[2*idx]+seg[2*idx+1])%mod;

 }

 lli qry(int idx,int start,int end,int ups,int upe)
  {
  if(start>end || upe<start || ups>end)
   {
    return 0 ;
  }
  else if(start>=ups && end<=upe)
   {
 
    return seg[idx] ;
}
int mid=(start+end)/2;
lli q1= qry(2*idx,start,mid,ups,upe);
lli q2= qry(2*idx+1,mid+1,end,ups ,upe);
return (q1+q2)%mod;
  }
  bool comp(pair<int,int> p1,pair<int,int> p2)
   {
    if(p1.first<p2.first) return true;
    else if(p1.first==p2.first && p1.second>p2.second) return true;
    else return false;
   }
int main()
{
int t;
cin>>t;
int cas=1;
while(t--)
{

memset(seg,0,sizeof seg);
int n;
v.clear();
cin>>n;
for(int i=1;i<=n;i++)
 {
   int a;
    scanf("%d",&a);
    v.push_back({a,i});
  }
  sort(v.begin(),v.end(),comp);
   update(1,0,n,0,0,1);
  for(int i=0;i<n;i++)
   {
    int num=v[i].first;
    int idx=v[i].second;
    int count=qry(1,0,n,0,idx-1);
    update(1,0,n,idx,idx,count);
   
}
lli ans=qry(1,0,n-1,1,n);
printf("Case %d: %lld\n",cas++,ans);
}
}

Watan And Dominoes Solved( number of numbers < than ith element )

Watan And Dominoes

All submissions for this problem are available.

Watan likes the game of Dominoes where a series of rectangular wooden pieces are placed on a line, hitting the right piece makes the rest of the pieces fall. In original version of the game, all the pieces are identical. But unfortunately the pieces that Watan has, have different heights. So, whether the pieces will fall or not becomes more difficult to predict. Watan is good at mathematics. He devised his own formula to predict the outcome. In his formula, he requires to find for each pieces, how many pieces appearing before it are smaller than it. This part is tedious and he doesn't want to spend a lot of time on it. So he comes to you to write a program to find this for him.

Input

The first line of the input contains a single integer T denoting the number of test cases. Each test case T has two lines. First line contains a single integer N denoting number of pieces present. Next line contains N space separated integers A_i denoting height of each piece.

Output

For each test case, output N space separated integers B_i where B_i is the number of elements A_j (1<=j<=i-1) which are less than A_i.

Constraints

• 1 <= T <= 1000
• 1 <= A_i <= 10^6
• 1 <= N <= 10^6

Sample Cases

Input
1
5
1 2 3 4 5

Output
0 1 2 3 4

------------------------------------------------------------------editorial----------------------------------------------------------------

  start processing from the first element to last update any number , and query  from 0 to till the number

-----------------------------------------------------------------------code-------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef int  lli;

int v[1000010];

lli seg[10000000];

int ans[10000000];

void update(int idx,int start,int end,int ups,int upe,lli val)

 {

  if(start>end || upe<start || ups>end) return ;

  else if(start==end && start==ups)

   {

   seg[idx]+=val;

   return ;

 }

 int mid=(start+end)/2;

 

 update(2*idx,start,mid,ups,ups,val);

 update(2*idx+1,mid+1,end,ups,upe,val);

 seg[idx]=seg[2*idx]+seg[2*idx+1];

 

 }

 lli  qry(int idx,int start,int end,int qs,int qe)

 {

  if(start>end || qe<start || qs>end) return 0;

 

  else if(start>=qs && end<=qe)

   {

   

   return seg[idx];

 }

 int mid=(start+end)/2;

lli q1= qry(2*idx,start,mid,qs,qe);

lli q2= qry(2*idx+1,mid+1,end,qs,qe);

  return (q1+q2);

  

 }

int main()

 {

  int t;

  cin>>t;

  while(t--)

   {

    memset(seg,0,sizeof seg);

   int n;

  cin>>n;

  int val=0;

  for(int i=0;i<n;i++)

    {

  int a; 

  scanf("%d",&v[i]);

  val=max(val,v[i]);

   }

   

 for(int i=0;i<n;i++)

  {

       int num=v[i];

       int count =qry(1,0,val,0,num-1);

       ans[i]=count;

       update(1,0,val,num,num,1);

  }

  for(int i=0;i<n;i++)

  printf("%d ",ans[i]);

   printf("\n");

    }

 }

1081 - Square Queries

1081 - Square Queries

PDF (English)

Statistics

Forum

Time Limit: 3 second(s)

Memory Limit: 64 MB

Little Tommy is playing a game. The game is played on a 2D N x N grid. There is an integer in each cell of the grid. The rows and columns are numbered from 1 to N.

At first the board is shown. When the user presses a key, the screen shows three integers I, J, S which designates a square (I, J) to (I+S-1, J+S-1) in the grid. The player has to predict the largest integer found in this square. The user will be given points based on the difference between the actual result and the given result.

Tommy doesn't like to lose. So, he made a plan, he will take help of a computer to generate the result. But since he is not a good programmer, he is seeking your help.

Input

Input starts with an integer T (≤ 3), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 500), Q (0 ≤ Q ≤ 50000). Each of the next N lines will contain N space separated integers forming the grid. All the integers will be between 0 and 10⁵.

Each of the next Q lines will contain a query which is in the form I J S (1 ≤ I, J ≤ N and 1 ≤ I + S, J + S < N and S > 0).

Output

For each test case, print the case number in a single line. Then for each query you have to print the maximum integer found in the square whose top left corner is (I, J) and whose bottom right corner is(I+S-1, J+S-1).

Sample Input	Output for Sample Input
1 4 5 67 1 2 3 8 88 21 1 89 12 0 12 5 5 5 5 1 1 2 1 3 2 3 3 2 1 1 4 2 2 3	Case 1: 88 21 12 89 88

Note

Dataset is huge. Use faster i/o methods.

---------------------------------------------------EDITORIAL------------------------------------------------------

THIS PROBLEM CAN BE SOLVED USING DP OR SEGMENT TREE BUT DP SOLUTION WILL  NOT PASS SINCE 500*500*500 MEMORY IS NOT ALLOWED ,

  

DP SOLUTION 

#include<bits/stdc++.h>

using namespace std;

int dp[501][501][501];

int main()

 {

  int t;

  cin>>t;

  int cas=1;

  while(t--)

  {

  memset(dp,0,sizeof dp);

  int n,q;

  cin>>n>>q;

  for(int i=1;i<=n;i++)

   {

     

      for(int j=1;j<=n;j++)

     scanf("%d",&dp[i][j][1]);

}

for(int k=2;k<=501;k++)

{

for(int i=1;i<=n;i++)

 {

  for(int j=1;j<=n;j++)

   {

    if(i+k-1<=n && j+k-1<=n)

          {

           

          int val1=max(dp[i][j][k-1],dp[i][j+1][k-1]);

           int val2=max(dp[i+1][j][k-1],dp[i+1][j+1][k-1]);

           dp[i][j][k]=max(val1,val2);

     // cout<<" i "<<i<<" j "<<j<<" k "<<k<< dp[i][j][k]<<endl;

  }

}

  }

}

cout<<"Case "<<cas++<<": "<<endl;

for(int i=0;i<q;i++)

 {

  int a,b,c;

   cin>>a>>b>>c; printf("%d \n",dp[a][b][c]);

 }

 

 }

 return 0;

 

 }

-----------------------------------------------seg tree approach ------------------------------------------

create seg tree  for each row separately now for each query apply range max in rows including  in that

row 

------------------------------------------------code--------------------------------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define pf printf

#define S(x) scanf("%d", &x)

#define SL(x) scanf("%ld", &x)

#define out(C) printf("Case %d:\n", C);

#define FOR(i, x, y) for(int i=x; i<=y; i++)

#define MID(a,b) ((a+b)>>1)

#define mx 100010

template<class T>inline bool read(T &x) {

    int c=getchar();

    int sgn=1;

    while(~c&&c<'0'||c>'9') {

        if(c=='-')sgn=-1;

        c=getchar();

    }

    for(x=0; ~c&&'0'<=c&&c<='9'; c=getchar())x=x*10+c-'0';

    x*=sgn;

    return ~c;

}

int grid[510][510];

int r,q;

int st[1700][1700];

void update (int tree[], int node, int l, int r, int x, int val){

//    cout<<node<<" "<<l<<" "<<r<<" "<<x<<" "<<val<<endl;

    if(l>x or r<x)return;

    if(l==x and r==x){

        tree[node]=val;

        return;

    }

    int m=MID(l,r);

    update(tree, node*2, l, m, x, val);

    update(tree, node*2+1, m+1, r, x, val);

    tree[node]=max(tree[node*2],tree[node*2+1]);

}

int query(int tree[], int node, int l, int r, int x, int y){

    if(l>=x and r<=y)

        return tree[node];

    int m = MID(l,r);

    int ret=-1;

    if(m>=x)

        ret=query(tree,node*2, l, m, x, y);

    if(m<y)

        ret=max(ret, query(tree,node*2+1,m+1,r,x,y));

    return ret;

}

int main() {

    int test;

    read(test);

    FOR(C, 1, test) {

        out(C);

        read(r);read(q);

        for(int i=1;i<=r;i++){

            fill(st[i],st[i]+(r*3), -1);

            for(int j=1;j<=r;j++){

                read(grid[i][j]);

                update(st[i],1,1,r,j,grid[i][j]);

            }

        }

//        cout<<"ok"<<endl;

        while(q--){

            int x1,y1,y;

            read(x1);read(y1);read(y);

            int x2=x1+y-1,y2=y1+y-1;

            int ans=-1;

            for(int i=x1; i<=x2;i++){

                ans = max(ans, query(st[i],1,1,r,y1,y2));

            }

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

        }

    }

    

}