Submission #1027609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027609		Otalp	Fire (BOI24_fire)	C++14	53 / 100	116 ms	8232 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

pii a[200100];

void solve(){
    int n, m;
    cin>>n>>m;
    int ok = 0;
    vector<int> q;
    vector<pii> d;
    pii mx = {1e9, 1e9};
    for(int i=1; i<=n; i++){
        cin>>a[i].ff>>a[i].ss;
        if(a[i].ff > a[i].ss){
            q.pb(i);
            mx = min(mx, {a[i].ff, i});
            d.pb({0, a[i].ss});
            d.pb({a[i].ff, m});
        }
        else{
            d.pb(a[i]);
        }
    }   
    if(q.size() == 0){
        cout<<-1<<'\n';
        return;
    }

    sort(d.begin(), d.end());
    int ans = 1e9;
    int j = mx.ss;
    {
        int s=a[j].ss, e=a[j].ff;
        int ls = -1, g = s;
        int res = 1;
        while(g < e){
            int mx = g;
            res ++;
            while(ls + 1 < d.size() and d[ls + 1].ff <= g){
                ls++;
                mx = max(mx, d[ls].ss);
            }
            if(mx == g){
                res = 1e9;
                break;
            }
            g = mx;
        }
        //cout<<a[j].ff<<' '<<a[j].ss<<' '<<ls<<'\n';
        ans = min(ans, res);
    }
    if(ans == 1e9) cout<<-1;
    else cout<<ans;
                
                




}

signed main(){
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             while(ls + 1 < d.size() and d[ls + 1].ff <= g){
      |                   ~~~~~~~^~~~~~~~~~
Main.cpp:14:9: warning: unused variable 'ok' [-Wunused-variable]
   14 |     int ok = 0;
      |         ^~

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