Benelux Algorithm Programming Contest 2014 Final - E - Excellent Engineers

Posted by WildCow on July 12, 2018

Excellent Engineers

Time Limit: 2000
Memory Limit: 262144K

Description

You are working for an agency that selects the best software engineers from Belgium, the Netherlands and Luxembourg for employment at various international companies. Given the very large number of excellent software engineers these countries have to offer, the agency has charged you to develop a tool that quickly selects the best candidates available from the agency’s files.

Before a software engineer is included in the agency’s files, he has to undergo extensive testing. Based on these tests, all software engineers are ranked on three essential skills: communication skills, programming skills, and algorithmic knowledge. The software engineer with rank one in the category algorithmic knowledge is the best algorithmic expert in the files, with rank two the second best, etcetera.

For potential customers, your tool needs to process the agency’s files and produce a shortlist of the potentially most interesting candidates. A software engineer is a potential candidate that is to be put on this shortlist if there is no other software engineer in the files that scores better on all three skills. That is, an engineer is to be put on the shortlist if there is no other software engineer that has better communication skills, better programming skills, and more algorithmic knowledge.

Input

On the first line one positive number: the number of test cases, at most 100100. After that per test case:

  • one line with a single integer $n (1 \le n \le 10^5)$, the number of software engineers in the agency’s files.
  • $n$ lines, each with three space-separated integers $r_1r , r_2,r_3(1 \le r_1, r_2, r_3 \le n)$: the rank of each software engineer from the files with respect to his communication skills, programming skills and algorithmic knowledge, respectively.

For each skill $s$ and each rank $x$ between $1$ and $n$, there is exactly one engineer with $r_s = x$

Output

Per test case:

  • one line with a single integer: the number of candidates on the shortlist.

Sample Input

3
3
2 3 2
3 2 3
1 1 1
3
1 2 3
2 3 1
3 1 2
10
1 7 10
3 9 7
2 2 9
5 10 8
4 3 5
7 5 2
6 1 3
9 6 6
8 4 4
10 8 1

Sample Output

1
3
7


考完后久违的写题
给你 $n$ 个满足偏序关系的三元组
如果其中一个元素小于另一个元素
就会把那个元素给吃了
问你最后会剩下多少个元素

三位偏序
很显然可以通过对 $x$ 排序降维
然后遍历 $x$
对于到第 $i$ 个元素的时候
显然 $x_i$ 肯定会比之前的更大
所以他不被吃的充要条件是
对于之前出现过的 $y < y_i$
所对应的 $z > z_i$
所以我们对于 $<y,z>$ 建立线段树
每次对于一个新元素
查询区间 $[1, y_i - 1]$ 的最小值
如果最小值小于 $z_i$
就跳过
否则就把 $<y_i, z_i>$ 插入线段树中
即 $y_i = z_i$


#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

struct Node
{
    int x;
    int y;
    int z;
};

struct Tree
{
    int l;
    int r;
    int minn;
};

Tree tree[N << 2];
Node node[N];
int n;

bool cmp(Node a, Node b)
{
    return a.x < b.x;
}

void Up(int x)
{
    tree[x].minn = min(tree[x << 1].minn, tree[x << 1 | 1].minn);
}

void Build(int x, int l, int r)
{
    tree[x].l = l;
    tree[x].r = r;
    tree[x].minn = INF;
    if(l == r){
        return;
    }
    else{
        int mid;

        mid = l + ((r - l) >> 1);
        Build(x << 1, l, mid);
        Build(x << 1 | 1, mid + 1, r);
        Up(x);
    }
}

void Update(int x, int l, int r, int v)
{
    int ll;
    int rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(l > r){
        return ;
    }
    if(ll == l && rr == r){
        tree[x].minn = v;
    }
    else{
        int mid;
    
        mid = ll + ((rr - ll) >> 1);
        Update(x << 1, l, min(mid, r), v);
        Update(x << 1 | 1, max(mid + 1, l), r, v);
        Up(x);
    }
}

int Quary(int x, int l, int r)
{
    int ll;
    int rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(l > r){
        return INF;
    }
    if(ll == l && rr == r){
        return tree[x].minn;
    }
    else{
        int mid;
        int t;
    
        t = INF;
        mid = ll + ((rr - ll) >> 1);
        t = min(t, Quary(x << 1, l, min(r, mid)));
        t = min(t, Quary(x << 1 | 1, max(mid + 1, l), r));
        Up(x);
    
        return t;
    }
}

int main(int argc, char const *argv[])
{
    int ncase;
    int ans;

    scanf("%d", &ncase);
    while(ncase --){
        ans = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i ++){
            scanf("%d%d%d", &node[i].x, &node[i].y, &node[i].z);
        }
        sort(node, node + n, cmp);
        Build(1, 1, n);
        for(int i = 0; i < n; i ++){
            if(Quary(1, 1, node[i].y - 1) < node[i].z){
                continue;
            }
            else{
                ans ++;
                Update(1, node[i].y, node[i].y, node[i].z);
            }
        }
        printf("%d\n", ans);
    }
    
    return 0;
}