Submission #1156000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156000		adiyer	Fire (BOI24_fire)	C++20	100 / 100	221 ms	46228 KiB

Main

#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")

#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 = 2e5 + 3; 
const int MAX = 2e4 + 11;
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, m, res;
ll l[N], r[N], to[N], ord[N], up[N][20];

bool cmp(ll i, ll j){
  return l[i] < l[j];
}

pair < ll, ll > t[4 * N];

void upd(ll k, ll x, ll v = 1, ll l = 1, ll r = n){
  if(l == r){ t[v] = {x, l}; return; }
  ll md = (l + r) / 2;
  if(k <= md) upd(k, x, v + v, l, md);
  else upd(k, x, v + v + 1, md + 1, r);
  t[v] = max(t[v + v], t[v + v + 1]);
}

pair < ll, ll > get(ll tl, ll tr, ll v = 1, ll l = 1, ll r = n){
  if(r < tl || tr < l) return {-inf, 0};
  if(tl <= l && r <= tr) return t[v];
  ll md = (l + r) / 2;
  return max(get(tl, tr, v + v, l, md), get(tl, tr, v + v + 1, md + 1, r));
}

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(l[i] > r[i]) r[i] += m;
  }
  sort(ord + 1, ord + n + 1, cmp);
  for(ll i = 1; i <= n; i++) upd(i, r[ord[i]]);
  for(ll i = 1; i <= n; i++){
    ll tl = i, tr = n + 1;
    while(tr - tl > 1){
      ll md = (tl + tr) / 2;
      if(l[ord[md]] <= r[ord[i]]) tl = md;
      else tr = md; 
    }
    to[i] = get(i, tl).S;
  }
  for(ll i = 1; i <= n; i++) up[i][0] = to[i]; 
  for(ll i = n; i >= 1; i--)
    for(ll j = 1; j < 20; j++) 
      up[i][j] = up[up[i][j - 1]][j - 1];
  for(ll i = 1; i <= n; i++){
    ll v = i, x = (l[ord[i]] + m - 1), k = 0;
    for(ll j = 19; j >= 0; j--)
      if(r[ord[up[v][j]]] < x)
        v = up[v][j], k |= (1 << j);  
    v = up[v][0], k++, k++;
    if(r[ord[v]] >= x) res = min(res, k);
  }
  if(res == inf) res = -1;
  cout << res;
}

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