Submission #1141607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141607		Rafiullah	Fire (BOI24_fire)	C++20	40 / 100	2095 ms	12976 KiB

Main

#include<bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int mod1 = 998244353;
const int LG = 20;
// #define s(i) (*s.find_by_order(i)) // Warning : Read this line.
set<pair<int,int>> S;
int power(int b,int e){
    if(e<=0)return 1;
    int o = power(b,e>>1);
    o *= o, o %= mod1;
    if(e % 2)o *= b, o %= mod1;
    return o;
}

void solve(){
    int n,m;cin >> n >> m;
    S.clear();
    for(int i = 1 ; i <= n ; i ++){
        int s,e;cin >> s >> e;
        S.insert({s,e});
    }
    set<pair<int,int>> T;
    for(auto a : S)
        if(a.first > a.second)T.insert(a);
    
    for(auto a : T){
        S.erase(a);
        S.insert({a.first, a.second + m});
    }
    T.clear();
    for(auto a : S)
        for(auto b : S){
            if(a==b)continue;
            if(a.first <= b.first and b.second <= a.second)
                T.insert(b);
        }
    for(auto a : T)
        S.erase(a);
    vector<pair<int,int>> g;
    for(auto a : S){
        g.push_back(a);
        if(a.second + m < 2 * m)g.push_back({a.first + m, a.second + m});
    }
    vector<int> next(3 * n);
    int sz = g.size();
    for(int i = 0 ; i < sz ; i ++){
        int how=0,ind=-1;
        for(int j = 0 ; j < sz ; j ++){
            if(i==j)continue;
            if(g[j].second <= g[i].second)continue;
            if(g[j].second - g[i].second > how and g[j].first <= g[i].second)
                ind = j, how = g[j].second - g[i].second;
        }
        next[i] = ind;
    }
    // for(auto i : g){
    //     cout << i.first << ' ' << i.second << '\n';
    // }
    int tot = 1e18;
    for(int i = 0 ; i < sz ; i ++){
        int ans = 1;
        int d = g[i].second-g[i].first;
        int r = i;
        while(d<m){
            int p = r;
            r = next[r];
            if(r == -1){ans=-1;break;}
            d += g[r].second - g[p].second;
            ans ++;
        }
        if(ans > -1)
            tot = min(tot, ans);
    }
    if(tot == 1e18)tot = -1;
    cout << tot << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

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