1366-B, *1300

Problem - 1366B - Codeforces

문제

• 순열 $a_{1}a_{2}...a_{n},\ (1\leq n\leq 10^{9})$에서 $a_{x} = 1$이고 나머지는 0
• 구간 $[l,\ r]$ 내의 두 index 값을 한번 바꾼다. $a_{i},\ a_{j} = a_{j},\ a_{i}$ ~ operation shuffle
• shuffle 은 $m(1\leq m \leq 100)$번 수행한다

 

$O(tm)$

1이 존재할 수 있는 index 의 왼쪽과 오른쪽 끝을 각각 $lp,\ lp$에 저장하자
구간 $[l,\ r]$이 주어졌을 때, $lp$, 혹은 $rp$가 이 구간에 포함된다면 1을 주어진 구간까지도 옮길 수 있다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
 
ll n, x;
int m;
ll lp, rp;
ll l, r;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n >> x >> m;
        lp = rp = x;
        while(m--){
            cin >> l >> r;
            if(r < lp || rp < l) continue;
            lp = min(lp, l);
            rp = max(rp, r);
        }
        cout << rp - lp + 1 << endl;
    }
 
    return 0;
}cs