Proficient.
Put your skills to the test.

Problem summary

Each fighter has attributes (A,B). In a fight, x may defeat y exactly when A[x]≥A[y] or B[x]≥B[y]. A loser is eliminated; fights can be scheduled in any order. For each fighter, decide whether some sequence of N−1 fights makes that fighter the sole survivor.

Constraints

1 ≤ N ≤ 10⁶; 0 ≤ A[i],B[i] ≤ 10⁹.

Worked example

An independently prepared example for this explanation.

4
4 4
1 3
3 7
2 6

WLWW

Solution analysis

1. Draw an edge x→y when x can defeat y. A fighter can win exactly when it can reach every vertex: the elimination history gives a directed tree of victories from the final winner, and conversely an outward spanning tree can be eliminated from its leaves upward. Every pair has at least one edge, so the strongly connected components are totally ordered by victory direction. The unique source component contains exactly all possible winners.
2. Find one vertex in that source component by a single scan. Keep a candidate; replace it whenever the next fighter can defeat it. At the component level a replacement can only move to an earlier, stronger component. Once a source-component fighter has appeared, the candidate can never leave that component.
3. Now search backward from the candidate. The vertices that can reach a source-component vertex are exactly that component. To avoid building a quadratic graph, keep all undiscovered vertices in two ordered sets, one by A and one by B. From v, discover every remaining vertex with A≥A[v] or B≥B[v], removing each from both sets. Each vertex is removed once. In the example fighters 1,3,4 are mutually reachable, while fighter 2 cannot reach any of them.

Why it works

Any two distinct strongly connected components have edges in only one direction; otherwise they would merge, and the existence of an edge for each vertex pair orders these components acyclically with a unique source. Exactly source vertices reach all vertices, establishing the winner characterization. The scan ends in this source because replacements cannot move backward in that order and every source vertex defeats every vertex outside it. The ordered-set traversal follows exactly all reverse edges to undiscovered vertices, so it finds precisely the source component and marks precisely the possible winners.

Watch out. The victory condition is OR and uses ≥. A fighter need not personally defeat everyone. Preserve original indices when reporting winners.

An independently written complete program with standard headers.

#include<iostream>
#include<set>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n),b(n);
    int candidate=0;
    set<pair<int,int>>byA,byB;
    for(int i=0;i<n;++i){
        cin>>a[i]>>b[i];
        byA.insert({a[i],i});
        byB.insert({b[i],i});
        if(a[i]>=a[candidate]||b[i]>=b[candidate]){
            candidate=i;
        }
    }
    string answer(n,'L');
    vector<int>pending;
    auto discover=[&](int vertex){
        byA.erase({a[vertex],vertex});
        byB.erase({b[vertex],vertex});
        answer[vertex]='W';
        pending.push_back(vertex);
    };
    discover(candidate);
    while(!pending.empty()){
        int vertex=pending.back();
        pending.pop_back();
        // Reverse edges come from vertices large enough in either attribute.
        while(!byA.empty()&&byA.rbegin()->first>=a[vertex]){
            discover(byA.rbegin()->second);
        }
        while(!byB.empty()&&byB.rbegin()->first>=b[vertex]){
            discover(byB.rbegin()->second);
        }
    }
    cout<<answer<<'\n';
}