Submission #1027616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027616		Otalp	Fire (BOI24_fire)	C++14	100 / 100	183 ms	34072 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
#define mp make_pair

pii a[200100];
pii pref[400100];
int jmp[400100][20];

void solve(){
    int n, m;
    cin>>n>>m;
    int ok = 0;
    vector<int> q;
    vector<pii> d;
    for(int i=1; i<=n; i++){
        cin>>a[i].ff>>a[i].ss;
        if(a[i].ff > a[i].ss){
            q.pb(i);
            d.pb({0, a[i].ss});
            d.pb({a[i].ff, m});
        }
        else{
            d.pb(a[i]);
        }
    }   
    sort(d.begin(), d.end());
    pref[0] = {d[0].ss, 0};
    for(int i=1; i<d.size(); i++){
        pref[i] = max(pref[i-1], {d[i].ss, i});
    }
    for(int i=0; i<d.size(); i++){
        int g = lower_bound(d.begin(), d.end(), mp(d[i].ss, (int)1e9 + 1)) - d.begin() - 1;
        jmp[i][0] = pref[g].ss;
    }
    for(int k=1; k<20; k++){
        for(int i=0; i<d.size(); i++){
            jmp[i][k] = jmp[jmp[i][k-1]][k-1];
        }
    }
    int ans = 1e9;
    for(int j: q){
        int s=a[j].ss, e=a[j].ff;
        int g = lower_bound(d.begin(), d.end(), mp(a[j].ss, (int)1e9 + 1)) - d.begin() - 1;
        g = pref[g].ss;
        int res = 2;
        for(int i=19; i>=0; i--){
            int k = jmp[g][i];
            if(d[k].ss >= e) continue;
            g = jmp[g][i];
            res += (1 << i);
        }
        int k = jmp[g][0];
        //cout<<d[k].ff<<' '<<d[k].ss<<'\n';
        if(d[g].ss < e) res++;
        if(d[k].ss < e){
            res = 1e9;
        }
        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:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=1; i<d.size(); i++){
      |                  ~^~~~~~~~~
Main.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0; i<d.size(); i++){
      |                  ~^~~~~~~~~
Main.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i=0; i<d.size(); i++){
      |                      ~^~~~~~~~~
Main.cpp:47:13: warning: unused variable 's' [-Wunused-variable]
   47 |         int s=a[j].ss, e=a[j].ff;
      |             ^
Main.cpp:17:9: warning: unused variable 'ok' [-Wunused-variable]
   17 |     int ok = 0;
      |         ^~

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