Question Name:Monk meets Dynamic Array

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fre freopen("in.txt","r",stdin)
#define pii pair<pair<int,int>, int>
#define f first
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define pi pair<int,int>
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int N,Q,t,l,r,x;
    cin >> N >> Q;
    assert(N<=1000000 and Q<=1000000);
    vector<int>V,LIS;
    vector<pi>UPD;
    for(int i=1;i<=N;i++) {
        cin >> x;
        V.pb(x);
        if(LIS.size()==0 or LIS.back()<x) {
        	LIS.pb(x);
        	UPD.pb({-1,x});
        }
        else{
        	int j = lower_bound(LIS.begin(),LIS.end(),x)-LIS.begin();
        	UPD.pb({j,LIS[j]});
        	LIS[j] = x;
        }
        assert(x<=1000000);
    }
    while(Q--) {
        cin >> t ;
        if(t==1) {
            cin >> x;
            assert(x<=1000000);
            V.pb(x);
            if(LIS.size()==0 or LIS.back()<x) {
	        	LIS.pb(x);
	        	UPD.pb({-1,x});
	        }
	        else{
	        	int j = lower_bound(LIS.begin(),LIS.end(),x)-LIS.begin();
	        	UPD.pb({j,LIS[j]});
	        	LIS[j] = x;
	        }
        }
        else if(t==2) {
            assert(V.size()>=0);
            V.pop_back();
			int j = UPD.back().f;
			int val = UPD.back().s;
			UPD.pop_back();
			if(j!=-1){
				LIS[j] = val;
			}
			else{
				LIS.pop_back();
			}
        }
        cout << LIS.size() << "\n";
    }
}
  • Problem Description
    In order to explore new things, Monk went to see the “Algo Show”, where he saw a dynamic array A1,A2…AN. The array made the show very interesting, by processing Q operations on itself.

    The operations are of following two types: 
    1 X : means push element X at the back of the array.
    2 : means pop the last element of the array.

    Note: It is guaranteed that, no pop operation will be applied on the empty array in the given input.

    In order to make the show more interactive, after preforming each operation, the array asked the length of the Longest Increasing Subsequence (LIS) of the resulting array from the audience.
    Being greedy for fame in the new world, Monk wants to answer all of the questions asked by the dynamic array. 
    Help Monk for the same.

    INPUT:
    First line of input will consists two integers N and Q. Next line will consists of N integers denoting the initial array. Next Q line will consists of operations described above.

    OUTPUT:
    After each operation, output the length of Longest increasing subsequence of the resulting array in new line.

    CONSTRAINTS:
    1 N 10^6
    1 Q 10^6
    1 Ai,x 10^6
  • Test Case 1
    Input (stdin)4 3
    1 2 3 2
    1 3
    2
    1 5
    Expected Output3
    3
    4
  • Test Case 2
    Input (stdin)5 4
    1 2 3 2 1
    1 2
    1 3
    2
    1 5
    Expected Output3
    3
    3
    4

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.