Submission #1284079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284079		sujalxpro	Money (IZhO17_money)	C++20	0 / 100	0 ms	332 KiB

money

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define rev(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define pb push_back
#define pii pair<int,int>
#define endl '\n'
#define F first
#define S second
#define ary array<int, 3 > 
#define all(arr) arr.begin() , arr.end()
constexpr int mod = 998244353;

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

void yes(){cout << "Yes" << endl;}
void no(){cout << "No" << endl;}

int binpow(int a , int b, int m = mod){
	int res = 1;
	while(b){if(b&1)res = res * a % m ; a = a * a % m , b >>= 1;}
	return res;
}

int expo(int a , int b){
	int res = 1;
	while(b){if(b&1)res = res * a ; a = a * a  , b >>= 1;}
	return res;
}


int inv(int a , int m = mod){return binpow(a , m - 2 , m);}

pii addPr(pii A , pii B){
	A.F += B.F , A.S += B.S;
	return A;
}


int isIntersecting(pii A , pii B){
	return !(A.F > B.S || B.F > A.S);
}





template<class T> bool chmin(T&a, T b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool chmax(T&a, T b) { bool B = a < b; a = max(a,b); return B; }
int add(int a , int b , int m = mod){ return ((a + b) % m + m ) % m;}
int mul(int a , int b , int m = mod){ a %= m , b %= m ; return (a * b % m + m ) % m; }
void chadd(int& a , int b , int m = mod){ a = ((a + b) % m + m ) % m; }
void chmul(int& a , int b , int m = mod){ a %= m , b %= m ; a = ( a * b % m + m ) % m ; }


int sigma(int n ){ return n * (n + 1) / 2;}

int sigma(int l , int r){return sigma(r) - sigma(l - 1);}



class SparseTableMn {
private:
    int n, max_log;
    vector<vector<int>> table;

    // Merge function — change this to max, gcd, etc. if needed
    int merge(int a, int b) {
        return min(a, b);  // RMQ
    }
	
public:
    SparseTableMn(const vector<int>& arr) {
        n = arr.size();
        max_log = 32 - __builtin_clz(n); // ceil(log2(n))
        table.assign(max_log, vector<int>(n));

        // Level 0 (length 1 intervals)
        for (int i = 0; i < n; ++i)
            table[0][i] = arr[i];

        // Build higher levels
        for (int k = 1; k < max_log; ++k) {
            for (int i = 0; i + (1 << k) <= n; ++i) {
                table[k][i] = merge(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Query in range [l, r] (inclusive)
    int query(int l, int r) {
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len); // floor(log2(len))
        return merge(table[k][l], table[k][r - (1 << k) + 1]);
    }
};

class SparseTableMx {
private:
    int n, max_log;
    vector<vector<int>> table;

    // Merge function — change this to max, gcd, etc. if needed
    int merge(int a, int b) {
        return max(a, b);  // RMQ
    }
	
public:
    SparseTableMx(const vector<int>& arr) {
        n = arr.size();
        max_log = 32 - __builtin_clz(n); // ceil(log2(n))
        table.assign(max_log, vector<int>(n));

        // Level 0 (length 1 intervals)
        for (int i = 0; i < n; ++i)
            table[0][i] = arr[i];

        // Build higher levels
        for (int k = 1; k < max_log; ++k) {
            for (int i = 0; i + (1 << k) <= n; ++i) {
                table[k][i] = merge(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Query in range [l, r] (inclusive)
    int query(int l, int r) {
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len); // floor(log2(len))
        return merge(table[k][l], table[k][r - (1 << k) + 1]);
    }
};


struct BIT {
    // single point add, prefix query sum
    vector <int> val;
    int n, offset;
    BIT () = default;
    BIT (int _n, int _offset = 3) : n(_n + _offset * 2), offset(_offset) {
        val.assign(n, 0);
    }
    void add(int p, int v) {
        for (p += offset; p < n; p += p & (-p)) {
            val[p] += v;
        }
    }
    int query(int p) {
        int ans = 0;
        for (p += offset; p > 0; p -= p & (-p)) {
            ans += val[p];
        }
        return ans;
    }
    int query(int l, int r) {
        // query [l, r]
        return query(r) - query(l - 1);
    }
	
	void update(int p , int v){
		int curV = query(p , p);
		add(p , v - curV);
	}
	
    int kth (int k) {
        // 1-index, return kth smallest number
        // 1 <= k && k <= current size
        int ans = 0;
        for (int i = 1 << __lg(n); i > 0; i >>= 1) {
            if (ans + i < n && val[ans + i] < k) {
                k -= val[ans += i];
            }
        }
        return ans - offset + 1;
    }
};




 
 



int SQRT(int num){
	int lo = 1 , hi = 2000000000 , ans = 0;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(mid * mid <= num) ans = mid , lo = mid + 1;
		else hi = mid - 1;
	}
	return ans;
}
 


 
struct hasher{
	int base , mod;
	vector<int> hash , basepow;
	hasher(){
		
	}
	hasher(string s , int _base = 37 , int	 _mod = 1e9 + 7){
		base = _base;
		mod = _mod;
		int n = s.size();
		s = "#" + s + "#";
		
		hash.resize(n+2) , basepow.resize(n + 2);
		hash[0] = 0 , basepow[0] = 1;
		
		for(int i = 1 ; i <= n ; i++){
			
			hash[i] = hash[i-1] * base + (s[i] - 'a' + 1) ;
			hash[i] %= mod;
			basepow[i] = (basepow[i-1] * base)%mod;
		}
		
	}
	
	int getHash(int l , int r){
		int res = hash[r];
		res -= basepow[r - l + 1] * hash[l-1] ;
		res = (res%mod + mod )%mod;
		return res;
	}
	
};
 
struct doubleHasher{
	hasher hash1 , hash2;
	doubleHasher(){
		
	}
	doubleHasher(string s ){
		hash1 = hasher(s , 37 , 999999929);
		hash2 = hasher(s , 37 , 999999937);
	}
	
	int getHash(int l , int r){
		return (1LL << 32) * hash1.getHash(l , r ) +hash2.getHash(l , r);
	}
};


 
// struct hasher{
	// int base , mod;
	// vector<int> hash , basepow , rHash;
	// hasher(){
		
	// }
	// hasher(string s , int _base = 37 , int	 _mod = 1e9 + 7){
		// base = _base;
		// mod = _mod;
		// int n = s.size();
		// s = "#" + s + "#";
		
		// hash.resize(n+2) , basepow.resize(n + 2) , rHash.resize(n + 2);
		// hash[0] = 0 , basepow[0] = 1;
		
		// for(int i = 1 ; i <= n ; i++){
			
			// hash[i] = hash[i-1] * base + (s[i] - 'a' + 1) ;
			// hash[i] %= mod;
			// basepow[i] = (basepow[i-1] * base)%mod;
		// }
 
        // for(int i = n ; i >= 1 ; i--){
            // rHash[i] = rHash[i + 1] * base + (s[i] - 'a' + 1);
            // rHash[i] %= mod;
 
        // }
		
	// }
	
	// int getHash(int l , int r){
		// int res = hash[r];
		// res -= basepow[r - l + 1] * hash[l-1] ;
		// res = (res%mod + mod )%mod;
		// return res;
	// }
 
    // int getRevHash(int l , int r){
        // int res = rHash[l];
        // res -= basepow[r - l + 1] * rHash[r + 1];
        // res = (res % mod + mod) % mod;
        // return res;
    // }
	
	// int isPalindrome(int l , int r){
		// return getHash(l , r) == getRevHash(l , r);
	// }
	
// };
 
// struct doubleHasher{
	// hasher hash1 , hash2;
	// doubleHasher(){
		
	// }
	// doubleHasher(string s ){
		// hash1 = hasher(s , 37 , 999999929);
		// hash2 = hasher(s , 37 , 999999937);
	// }
	
	// int getHash(int l , int r){
		// return (1LL << 32) * hash1.getHash(l , r ) +hash2.getHash(l , r);
	// }
    // int getRevHash(int l , int r){
        // return (1LL << 32) * hash1.getRevHash(l , r) + hash2.getRevHash(l , r);
    // }
	// int isPalindrome(int l , int r){
		// return hash1.isPalindrome(l , r) && hash2.isPalindrome(l , r);
	// }
	
// };
 
 
vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;
	vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }
	vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> lcp_construction(const vector<int>& sfx , string& s){
	int n = sfx.size();
	
	vector<int> lcp(n);
	vector<int> isfx(n);
	for(int i = 0 ; i < n ; i++)isfx[sfx[i]] = i;
	
	for(int i = 0 , k = 0 ; i < n ; i++){
		int pos = isfx[i];
		if(pos == 0)continue;
		int j = sfx[pos - 1];
		
		while(i + k < n && j + k < n && s[i + k] == s[j + k])k++;
		lcp[pos] = k;
		if(k > 0)k--;
	}
	
	return lcp;
}

vector<int> suffix_array_construction(string s) {
    s.push_back('$');
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

struct DisjointSet{
    vector<int> p, sz;
public:
    DisjointSet(int n) : p(n + 1) , sz(n + 1 , 1) { iota(p.begin() , p.end() , 0);}
	int find(int x){ return (x == p[x]) ? x : p[x] = find(p[x]) ;}
	int same(int u , int v){return find(u) == find(v);}
	int size(int u){return sz[find(u)];}
	void merge(int u , int v){
		u = find(u) , v = find(v); if(u == v)return;
		if(sz[u] > sz[v])swap(u , v);
		p[u] = v , sz[v] += sz[u];
	}
};

struct segmentTree{
	struct node{
		int sum;
		node(int s = 0) : sum(s) {}
	};
	node merge(node a , node b){return node(a.sum + b.sum);}
	vector<node> tree;
	int n;
	segmentTree(int _n){n = _n; tree.resize(4 * n);}
	void update(int idx , int val , int id , int lo , int hi){
		if(idx < lo || idx > hi)return;
		if(lo == hi){tree[id].sum = val; return;}
		int mid = (lo + hi)/2;
		update(idx , val , id * 2 + 1 , lo , mid);
		update(idx , val , id * 2 + 2 , mid + 1 , hi);
		tree[id] = merge(tree[id * 2 + 1] , tree[id * 2 + 2]);
	}
	void update(int idx , int val){update(idx , val , 0 , 0 , n - 1);}
	
	node query(int l , int r , int id , int lo , int hi){
		if(hi < l || lo > r)return node();
		if(l <= lo && hi <= r)return tree[id];
		int mid = (lo + hi)/ 2;
		return merge(
			query(l , r , id * 2 + 1 , lo , mid) , 
			query(l , r , id * 2 + 2 , mid + 1 , hi)  
		);
	}
	int query(int l , int r){return query(l , r , 0 , 0 , n - 1).sum;}
};




 
struct lazySegmentTree{
	struct node{
		int sum , inc;
		node(int s = 0) : sum(s) , inc(0)  {}
	};
	node merge(node a , node b){return node(a.sum + b.sum);}
	vector<node> tree;
	int n;
	
	lazySegmentTree(int _n){n = _n; tree.resize(4 * n);}
	
	void push(int id , int lo , int hi){
		
		tree[id].sum += (hi - lo + 1) * tree[id].inc;
		if(lo != hi){
			tree[id * 2 + 1].inc += tree[id].inc;
			tree[id * 2 + 2].inc += tree[id].inc;
		}
		tree[id].inc = 0;
		
	}
	
	void add(int l , int r , int val , int id , int lo , int hi){
		push(id , lo , hi);
		if(lo > r || hi < l)return;
		if(l <= lo && hi <= r){
			tree[id].inc += val;
			push(id , lo , hi);
			return ;
		}
		int mid = (lo + hi) / 2;
		add(l , r , val , id * 2 + 1 , lo , mid);
		add(l , r , val , id * 2 + 2 , mid + 1 , hi);
		tree[id] = merge(tree[id * 2 + 1] , tree[id * 2 + 2]);
	}
	void add(int l , int r , int val){add(l , r , val , 0 , 0 , n-1);}
	
	
	
	node query(int l , int r , int id , int lo , int hi){
		push(id , lo , hi);
		if(lo > r || hi < l)return node();
		if(l <= lo && hi <= r)return tree[id];
		int mid = (lo + hi) / 2;
		return merge(
			query(l , r , id * 2 + 1 , lo , mid),
			query(l , r , id * 2 + 2 , mid + 1 , hi)
		);
	}
	int query(int l , int r){return query(l , r , 0 , 0 , n-1).sum;}
};

class SparseTableGcd {
private:
    int n, max_log;
    vector<vector<int>> table;

    // Merge function — change this to max, gcd, etc. if needed
    int merge(int a, int b) {
        return __gcd(a , b);  // RMQ
    }
	
public:
    SparseTableGcd(const vector<int>& arr) {
        n = arr.size();
        max_log = 32 - __builtin_clz(n); // ceil(log2(n))
        table.assign(max_log, vector<int>(n));

        // Level 0 (length 1 intervals)
        for (int i = 0; i < n; ++i)
            table[0][i] = arr[i];

        // Build higher levels
        for (int k = 1; k < max_log; ++k) {
            for (int i = 0; i + (1 << k) <= n; ++i) {
                table[k][i] = merge(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Query in range [l, r] (inclusive)
    int query(int l, int r) {
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len); // floor(log2(len))
        return merge(table[k][l], table[k][r - (1 << k) + 1]);
    }
};


 
const int root = binpow(3 , 119);
const int root_1 = binpow(root , mod-2);
const int root_pw = 1 << 23;
 
 
 
 
void fft(vector<int> & a, bool invert) {
    int n = a.size();
 
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
 
        if (i < j)
            swap(a[i], a[j]);
    }
 
    for (int len = 2; len <= n; len <<= 1) {
        int wlen = invert ? root_1 : root;
        for (int i = len; i < root_pw; i <<= 1)
            wlen = (int)(1LL * wlen * wlen % mod);
 
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; j++) {
                int u = a[i+j], v = (int)(1LL * a[i+j+len/2] * w % mod);
                a[i+j] = u + v < mod ? u + v : u + v - mod;
                a[i+j+len/2] = u - v >= 0 ? u - v : u - v + mod;
                w = (int)(1LL * w * wlen % mod);
            }
        }
    }
 
    if (invert) {
        int n_1 = binpow(n, mod -2);
        for (int & x : a)
            x = (int)(1LL * x * n_1 % mod);
    }
}
 
 
 
vector<int> multiply(vector<int>&  a, vector<int>&  b) {
    vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n );
    fb.resize(n);
 
    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] = (1LL*fa[i]*fb[i])%mod;
    fft(fa, true);
 
    vector<int> result(n);
    for (int i = 0; i < n; i++)
        result[i] = fa[i];
    
    result.resize(a.size() + b.size() - 1);
    return result;
}



void solve(){
	
	int n ; cin >> n;
	vector<int> a(n);
	for(auto& x : a)cin >> x;
	
	set<int> st;
	for(int i = 0 ; i < n ; i++){
		
		auto it = st.upper_bound(a[i]);
		if(it != st.begin()){
			it--;
			st.erase(it);
			st.insert(a[i]);
		}
		else{
			st.insert(a[i]);
		}
	}
	cout << st.size() << endl;
	
	
}





int32_t main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	
	int tt = 1; 
	cin >> tt;
	
	for(int i = 1 ; i <= tt ; i++){
		solve();
	}
	
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55