Submission #1022036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022036		huutuan	Fire (BOI24_fire)	C++14	100 / 100	298 ms	139204 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10, LG=20;
int n, m;
pair<int, int> a[N];
int jump[LG][N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   vector<int> v;
   for (int i=1; i<=n; ++i){
      cin >> a[i].first >> a[i].second;
      v.push_back(a[i].first);
      v.push_back(a[i].second);
      v.push_back(a[i].first+m);
      v.push_back(a[i].second+m);
      if (a[i].first>a[i].second) a[i].second+=m;
   }
   sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end())-v.begin());
   int _m=m;
   m=v.size();
   for (int i=0; i<m; ++i) jump[0][i]=i;
   for (int i=1; i<=n; ++i){
      int l=lower_bound(v.begin(), v.end(), a[i].first)-v.begin();
      jump[0][l]=max<int>(jump[0][l], lower_bound(v.begin(), v.end(), a[i].second)-v.begin());
   }
   for (int i=1; i<m; ++i) jump[0][i]=max(jump[0][i], jump[0][i-1]);
   for (int i=1; i<LG; ++i) for (int j=0; j<m; ++j) jump[i][j]=jump[i-1][jump[i-1][j]];
   int ans=1e9;
   for (int i=1; i<=n; ++i){
      int l=lower_bound(v.begin(), v.end(), a[i].first)-v.begin();
      int r=lower_bound(v.begin(), v.end(), a[i].first+_m)-v.begin();
      int cur=0;
      for (int j=LG-1; j>=0; --j) if (jump[j][l]<r){
         cur+=1<<j;
         l=jump[j][l];
      }
      ans=min(ans, cur+1);
   }
   cout << (ans>n?-1:ans) << '\n';
   return 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