Submission #1155670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155670		adiyer	Fire (BOI24_fire)	C++20	0 / 100	2096 ms	46216 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first 
#define S second 

using namespace std;

typedef long long ll;

const int N = 6e5 + 17; 
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, m, sz, res;
ll l[N], r[N], ord[N], was[N], d[N];

map < ll, ll > id;

vector < pair < ll, ll > > vec;
vector < pair < ll, ll > > g[N];

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m, res = inf;
  for(ll i = 1; i <= n; i++){ 
    cin >> l[i] >> r[i], ord[i] = i;
    if(r[i] < l[i]) r[i] = r[i] + m;
    vec.pb({l[i], r[i]});
    vec.pb({r[i], inf});
    vec.pb({l[i] + m - 1, inf});
  }
  vec.pb({2 * m + 1, 2 * m + 1});
  sort(all(vec));
  for(ll i = 0; i < len(vec); i++)
    if(!id[vec[i].F]) 
      id[vec[i].F] = ++sz;
  for(ll i = 0; i < len(vec); i++){
    if(vec[i].S != inf){
      ll l = i, r = len(vec) - 1;
      while(r - l > 1){
        ll md = (l + r) / 2;
        if(vec[md].F > vec[i].S) r = md;
        else l = md;
      }
      g[id[vec[i].F]].pb({id[vec[l].F], 1});
    }
    if(i){
      g[id[vec[i].F]].pb({id[vec[i - 1].F], 0});
    }
  }
  for(ll i = 0; i < len(vec); i++){
    if(vec[i].S == inf) continue;
    for(ll j = 1; j <= sz; j++) was[j] = d[j] = 0;
    deque < ll > q;
    q.push_front(id[vec[i].F]), was[id[vec[i].F]] = 1;
    while(len(q)){
      ll v = q.front();
      q.pop_front();
      for(auto [u, w] : g[v]){
        if(!was[u]){
          d[u] = d[v] + w, was[u] = 1;
          if(!w) q.push_front(u);
          else q.push_back(u);
        }
      }
    }
    for(ll j = 0; j < len(vec); j++){
      if(vec[i].F + m - 1 <= vec[j].F && was[id[vec[j].F]]){
        res = min(res, d[id[vec[j].F]]);
      }
    }
  }
  if(res == inf) res = -1;
  cout << res;
}

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