Algorithm


problem link- https://www.spoj.com/problems/NICEDAY/

NICEDAY - The day of the competitors

 

The International Olympiad in Informatics is coming and the leaders of the Vietnamese Team have to choose the best contestants all over the country. Fortunately, the leaders could choose the members of the team among N very good contestants, numbered from 1 to N (3 ≤ N ≤ 100000). In order to select the best contestants the leaders organized three competitions. Each of the N contestants took part in all three competitions and there were no two contestants with equal results on any of the competitions. We say that contestant А is better than another contestant В when А is ranked before В in all of the competitions. A contestant A is said to be excellent if no other contestant is better than A. The leaders of the Vietnamese Team would like to know the number of excellent contestants.

Input

First line of the input contains an integer t (1 ≤ t ≤ 10), equal to the number of test cases. Then descriptions of t test cases follow. First line of description contains the number of competitors N . Each of the next N lines describes one competitor and contains integer numbers ai, bi, ci (1 ≤ ai, bi, ci ≤ N ) separated by spaces, the order of i-th competitor's ranking in the first competition , the second competition and the third competition.

Output

For each test case in the input your program should output the number of excellent contestants in one line.

Note: Because the input is too large so we have 4 input files and the total time limit is 4s (not 1s).

Example

Input:
1
3
1 2 3
2 3 1
3 1 2

Output:
3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e5+5;
vector<pair<int, pair<int, int> > > table;
int BIT[MAXN];

void update(int idx, int val){
	while(idx <= 100000){
		BIT[idx] = min(BIT[idx], val);
		idx += idx&-idx;
	}
}

int query(int idx){
	int minn = 1 << 30;;
	while(idx > 0){
		minn = min(minn, BIT[idx]);
		idx -= idx&-idx;
	}
	return minn;
}

int main(){
    io;
    int t;
    cin >> t;
    while(t--){
    	int n;
    	cin >> n;
    	table.clear();
    	for(int i = 1;i <= 100000; i++)
    		BIT[i] = 1 << 30;;
    	for(int i = 0;i < n; i++){
    		int a, b, c;
    		cin >> a >> b >> c;
    		table.push_back({a,{b,c}});
    	}
    	sort(table.begin(), table.end());
    	int ans = 0;
    	for(int i = 0;i < n; i++){
    		int key = table[i].second.first;
    		int value = table[i].second.second;
    		int queryAns = query(key);
    		if(value < queryAns)
    			ans++;
    		update(key, value);
    	}
    	cout << ans << endl;
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
1
3
1 2 3
2 3 1
3 1 2

Output

x
+
cmd
3
Advertisements

Demonstration


SPOJ Solution-The day of the competitors-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python