Submission #1128913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128913		nhanhoang510	Fire (BOI24_fire)	C++20	27 / 100	175 ms	2000 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2 * 1e5 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

struct RANGE{
    int l, r;
};

bool cmp_RANGE(RANGE a, RANGE b){
    return a.l < b.l;
}

int n, m;
RANGE a[maxn];

namespace SUB1{

struct ITEM{
    int id, l, r;
};

bool cmp(ITEM a, ITEM b){
    return a.l < b.l;
}

const int maxN = 20 + 7;
ii getid[maxN];
bool ok[maxN];
int nn; ITEM arr[2 * maxN];

int N; RANGE b[maxN];

void solve(){
    nn = 0;
    for(int i = 1; i <= n; ++i) if(a[i].l <= a[i].r){
        ++nn;
        arr[nn] = {i, a[i].l, a[i].r};
    } else{
        ++nn;
        arr[nn] = {i, 1, a[i].r};
        ++nn;
        arr[nn] = {i, a[i].l, m};
    }
    sort(arr + 1, arr + nn + 1, cmp);
    for(int i = 1; i <= n; ++i) getid[i] = {-1, -1};
    for(int i = 1; i <= nn; ++i){
        int pos = arr[i].id;
        if(getid[pos].F == -1)
            getid[pos].F = i;
        else{
            getid[pos].S = getid[pos].F;
            getid[pos].F = i;
        }
    }

//    cerr << "--------------\n";
//    cerr << nn << "\n";
//    for(int i = 1; i <= nn; ++i){
//        cerr << arr[i].id << " " << arr[i].l << " " << arr[i].r << "\n";
//    }
//    cerr << "--------------\n";
//    for(int i = 1; i <= n; ++i){
//        cerr << getid[i].F << " " << getid[i].S << "\n";
//    }

    int ans = n + 1;
    int max_state = (1 << n);
    for(int state = 1; state < max_state; ++state){
        memset(ok, false, sizeof(ok));
        for(int i = 0; i < n; ++i) if(state & (1 << i)){
            ok[getid[i + 1].F] = true;
            if(getid[i + 1].S != -1)
                ok[getid[i + 1].S] = true;
        }
        N = 0;
        for(int i = 1; i <= nn; ++i) if(ok[i]){
            ++N;
            b[N] = {arr[i].l, arr[i].r};
        }
        bool check = true;
        int Max = 0;
        for(int i = 1; i <= N; ++i){
            int l = b[i].l, r = b[i].r;
            if(l - Max > 1){
                check = false;
                break;
            }
            Max = max(Max, r);
        }
        if(Max != m) check = false;
        if(check == true){
            ans = min(ans, __builtin_popcount(state));
        }
    }
    if(ans == n + 1)
        ans = -1;
    cout << ans << "\n";
    return;
}

}

int solve_st(RANGE a[]){
    sort(a + 1, a + n + 1, cmp_RANGE);
    int Maxx = 0; bool ok = true;
    for(int i = 1; i <= n; ++i){
        int l = a[i].l, r = a[i].r;
        if(l - Maxx > 1){
            ok = false;
            break;
        }
        Maxx = max(Maxx, r);
    }
    if(Maxx != m) ok = false;
    if(!ok){
        return -1;
    }
    int ans = 0, Max = 0, MaxAll = 0;
    for(int i = 1; i <= n; ++i){
        int l = a[i].l, r = a[i].r;
        if(l > Max + 1){
            ++ans;
            Max = MaxAll;
        }
        MaxAll = max(MaxAll, r);
        if(MaxAll == m){
            ++ans;
            break;
        }
    }
    return ans;
}

namespace SUB4{

void solve(){
    int ans = solve_st(a);
    cout << ans << "\n";
    return;
}

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        int l, r; cin >> l >> r;
        r = (r - 1 + m) % m;
        l = l + 1, r = r + 1;
        a[i] = {l, r};
    }
    if(n <= 20){
        SUB1::solve();
    } else
        SUB4::solve();
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 13 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26