Proficient.
Put your skills to the test.

Problem summary

Each flight request must be scheduled on one day within its inclusive availability interval. Two pilots form a crew; each crew flies at most once daily. Decide whether all requests fit on weekdays, require weekends, or are impossible even with weekends.

Constraints

N ≤ 10^9; M ≤ 10^6; P ≤ 2·10^6; 1 ≤ start ≤ end ≤ N.

Worked example

An independently prepared example for this explanation.

100 3 2
4 5
5 6
5 7

MIXED

Solution analysis

1. For a fixed choice of usable days, schedule requests greedily by earliest deadline. Sort by start day and keep available unfinished deadlines in a min-heap. A day provides floor(P/2) flight slots.
2. When the heap is empty, jump directly to the next request start. For weekday-only scheduling, skip Saturday and Sunday to the following Monday. Add every request released by the current day, reject an expired deadline, and fill available slots from the heap.
3. The sample has one crew. Request [4,5] can use Thursday and one of the other two can use Friday. The third requires a weekend, so weekday scheduling fails but unrestricted scheduling succeeds: output MIXED.

Why it works

If a feasible schedule uses a later-deadline available request in the next slot instead of the earliest-deadline request, exchange their scheduled days. Both remain released and the displaced request has a deadline no earlier, so feasibility is preserved. Repeating establishes the greedy schedule. Testing weekdays first and all days second distinguishes exactly the three outcomes.

Watch out. Capacity is floor(P/2), not P. Release and deadline days are inclusive. Avoid iterating through up to a billion empty days.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
// Algorithm: For a fixed choice of usable days, schedule requests greedily by earliest deadline.
using namespace std;
bool feasible(const vector<pair<int,int>>&requests,int crews,bool weekdaysOnly){
    if(crews==0){
        return requests.empty();
    }
    priority_queue<int,vector<int>,greater<int>>deadlines;
    int next=0,day=1;
    int count=static_cast<int>(requests.size());
    while(next<count||!deadlines.empty()){
        if(deadlines.empty()){
            day=max(day,requests[next].first);
        }
        int weekday=(day-1)%7;
        if(weekdaysOnly&&weekday>=5){
            day+=7-weekday;
        }
        while(next<count&&requests[next].first<=day){
            deadlines.push(requests[next++].second);
        }
        if(!deadlines.empty()&&deadlines.top()<day){
            return false;
        }
        for(int slot=0;slot<crews&&!deadlines.empty();++slot){
            deadlines.pop();
        }
        ++day;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,pilots;
    cin>>n>>m>>pilots;
    vector<pair<int,int>>requests(m);
    for(auto&request:requests){
        cin>>request.first>>request.second;
    }
    sort(requests.begin(),requests.end());
    if(feasible(requests,pilots/2,true)){
        cout<<"OK\n";
    }
    else if(feasible(requests,pilots/2,false)){
        cout<<"MIXED\n";
    }
    else{
        cout<<"IMPOSSIBLE\n";
    }
}