Problem Description

A coach needs to select athletes from n candidates. Each athlete has three physical attributes: endurance, power, and skill, represented as (e, p, s). An athlete i is considered dominated if there exists another athlete j with strictly higher values in all three dimensions (e_j > e_i, p_j > p_i, s_j > s_i). The task is to count all non-dominated athletes.

Core Concept: 3D Dominance

This is a classic 3D partial order problem. We need to count points that are not strictly dominated by any other point in three-dimensional space. The challenge is to do this efficient for n up to 100,000.

Solution Strategy

We can reduce the problem to a 2D query after fixing one dimension through sorting:

1. Sort by Endurance: Sort athletes by endurance in descending order. This ensures that when processing each athlete, all previously processed athletes have equal or higher endurance.
2. Handle Equal Endurance: For athletes with equal endurance, we must ensure they don't incorrectly dominate each other. We sort them by power in descending order, so an athlete is only compared against those with strictly higher endurance or same endurance but higher power.
3. 2D Query on Power and Skill: After sorting, we need to check if any prior athlete has both greater power and greater skill. This becomes a 2D dominance query.

Key Optimization: Coordinate Transformation

To efficiently query for athletes with greater power and skill, we transform coordinates:

• Let p' = n + 1 - p (transformed power)
• Let s' = n + 1 - s (transformed skill)

This transformation converts the condition "p_j > p_i AND s_j > s_i" into "p'_j < p'_i AND s'_j < s'_i", allowing us to use a prefix query.

Fenwick Tree for Minimum Queries

We use a Fenwick Tree (Binary Indexed Tree) to maintain the minimum transformed skill value (s') for each transformed power index (p'). For each athlete:

1. Query the minimum s' among all athletes with p' less than current p'.
2. If the returned value is ≥ current s', no prior athlete dominates the current one, so we count it.
3. Update the tree at position p' with the current s' (taking minimum).

Complexity Analysis

The algorithm runs in O(n log n) time due to sorting and Fenwick Tree operations, and uses O(n) space.

Implementation

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

struct Athlete {
    int endurance, power, skill;
    // Sort by endurance descending, then power descending
    bool operator<(const Athlete& other) const {
        if (endurance != other.endurance) 
            return endurance > other.endurance;
        return power > other.power;
    }
};

const int MAXN = 100000;
int n;
Athlete players[MAXN + 5];
int bit[MAXN + 5]; // Fenwick Tree storing minimum transformed skill

// Query minimum value in prefix [1, idx]
int queryMin(int idx) {
    int result = n + 1;
    while (idx > 0) {
        result = min(result, bit[idx]);
        idx -= idx & -idx;
    }
    return result;
}

// Update position idx with value val (keep minimum)
void updateMin(int idx, int val) {
    while (idx <= n) {
        bit[idx] = min(bit[idx], val);
        idx += idx & -idx;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n)) return 0;
    
    for (int i = 1; i <= n; i++) {
        cin >> players[i].endurance >> players[i].power >> players[i].skill;
        // Transform coordinates: p' = n+1-p, s' = n+1-s
        players[i].power = n + 1 - players[i].power;
        players[i].skill = n + 1 - players[i].skill;
        bit[i] = n + 1; // Initialize BIT
    }
    
    sort(players + 1, players + n + 1);
    
    int availableCount = 0;
    for (int idx = 1; idx <= n; idx++) {
        // Check if any prior athlete has both higher power and skill
        int minSkill = queryMin(players[idx].power - 1);
        if (minSkill >= players[idx].skill) {
            availableCount++;
        }
        updateMin(players[idx].power, players[idx].skill);
    }
    
    cout << availableCount;
    return 0;
}