1623-B

Problem - B - Codeforces

 

 

풀이

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
struct info{
    int l;
    int r;
    int d;
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<int> cnt(n);
        stack<pi> st;
        ooop(i, n){
            int s, e; cin >> s >> e;
            st.push({s, e});
            for(int j = s; j <= e; j++) cnt[j-1]++;
        }
 
        priority_queue<pi, vector<pi>, greater<> > pq;
        ooop(i, n) pq.push({cnt[i], i+1});
 
        vector<info> res;
        while(!pq.empty()){
            auto [_, d] = pq.top(); pq.pop();
            stack<pi> tmp;
            int is = 0, ie = -1;
            while(!st.empty()){
                auto [s, e] = st.top(); st.pop();
                if(s <= d && d <= e && ie - is < e - s){
                    if(ie != -1) tmp.push({is, ie});
                        ie = e; is = s;
                }
                else tmp.push({s, e});
            }
            res.push_back(info{is, ie, d});
            st = tmp;
        }
 
        for(auto [l, r, d]: res) cout << l << ' ' << r << ' ' << d << endl;
    }
 
    return 0;
}cs