Expert.
Put your skills to the test.

Problem summary

Fighter i has attributes A[i],B[i]. Fighter x can defeat y if A[x]≥A[y] OR B[x]≥B[y]. Losers leave the tournament. Determine who can become the sole survivor under some schedule.

Constraints

1 ≤ N ≤ 1000000; 0 ≤ A[i],B[i] ≤ 1000000000.

Worked example

Official statement example.

4
4 4
1 3
3 7
2 6

WLWW

Solution analysis

1. Direct an edge x→y when x can defeat y. A fighter can win exactly when it can reach all fighters: an elimination history supplies a tree of victories, and an outward spanning tree can conversely be eliminated from leaves toward its root. Every pair has at least one directed edge, so the strongly connected components are totally ordered, with winners precisely in the unique source component.
2. Sort fighters by increasing A. Across two distinct components every stronger fighter must have both coordinates strictly greater than every weaker fighter; otherwise there would be a reverse victory edge. Thus component boundaries are exactly cuts i where A[i]<A[i+1] and max B on the prefix is strictly smaller than min B on the suffix.
3. Precompute suffix minima of B and scan prefix maxima. The fighters after the last valid cut form the strongest component. In the sample the fighter (1,3) is separated from all others by such a cut; the remaining three form a mutually reachable component and can all win.

Why it works

Between distinct SCCs all edges point in one direction, since both directions would form a cycle in the condensation; semicompleteness makes their order total. A stronger component strictly dominates a weaker one in both coordinates, making each boundary contiguous in the A order and satisfying the stated cut inequalities. Conversely every stated cut forbids all edges from prefix to suffix and therefore separates components. Consequently the suffix after the last cut is exactly the source SCC, whose vertices are exactly all possible tournament winners.

Watch out. Equality in either coordinate permits victory both ways in that coordinate, so separating cuts require strict inequalities. A winner need not directly defeat everyone.

An independently written complete program with standard headers.

// Key idea: Between distinct SCCs all edges point in one direction, since both directions would form a
// cycle in the condensation; semicompleteness makes their order total. A stronger component strictly
// dominates a weaker one in both coordinates, making each boundary contiguous in the A order and
// satisfying the stated cut inequalities.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Fighter{
    int a,b,index;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Fighter>fighters(n);
    for(int i=0;i<n;++i){
        cin>>fighters[i].a>>fighters[i].b;
        fighters[i].index=i;
    }
    sort(fighters.begin(),fighters.end(),[](const Fighter&x,const Fighter&y){
        return x.a<y.a;
    });
    vector<int>suffix(n);
    suffix[n-1]=fighters[n-1].b;
    for(int i=n-2;i>=0;--i){
        suffix[i]=min(fighters[i].b,suffix[i+1]);
    }
    int firstWinner=0;
    int maximum=fighters[0].b;
    for(int i=0;i+1<n;++i){
        maximum=max(maximum,fighters[i].b);
        if(fighters[i].a<fighters[i+1].a&&maximum<suffix[i+1]){
            firstWinner=i+1;
        }
    }
    string answer(n,'L');
    for(int i=firstWinner;i<n;++i){
        answer[fighters[i].index]='W';
    }
    cout<<answer<<'\n';
}