Submission #991238

#	Time	Username	Problem	Language	Result	Execution time	Memory
991238		VMaksimoski008	Fire (BOI24_fire)	C++17	100 / 100	366 ms	96536 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int LOG = 20;
const int maxn = 2e5 + 5;

int up[maxn][LOG], depth[maxn];
vector<int> graph[maxn+5];

void dfs(int u, int p) {
    for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];

    for(int &v : graph[u]) {
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
}

struct SegTree {
    int n;
    vector<pii> tree, v;

    SegTree(vector<pii> _v) {
        v = _v;
        n = _v.size();
        tree.resize(4*n+5);
        build(1, 0, n-1);
    }

    pii merge(pii a, pii b) {
        if(a.first >= b.first) return a;
        return b;
    }

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u] = {v[tl].second, tl};
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }

    pii query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || l > tr || tl > r) return pii{0, 0};
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(
            query(2*u, tl, tm, l, r),
            query(2*u+1, tm+1, tr, l, r)
        );
    }

    pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, m, ans=1e9;
    cin >> n >> m;

    vector<pii> v(n);
    for(pii &x : v) cin >> x.first >> x.second;

    map<ll, ll> mp;
    for(int i=0; i<n; i++) {
        if(v[i].first > v[i].second) v[i].second = m + v[i].second;
        if(!mp.count(v[i].first)) mp[v[i].first] = v[i].second;
        else mp[v[i].first] = max(mp[v[i].first], v[i].second);
    }

    v.clear();
    for(auto &[a, b] : mp) {
        //cout << a << ' ' << b << '\n';
        v.push_back({ a, b });
    }

    sort(v.begin(), v.end());

    n = v.size();
    vector<int> out(n);

    SegTree tree(v);

    for(int i=0; i<n-1; i++) {
        int mx=0, id=-1;
        // for(int j=0; j<n; j++) {
        //     if(i == j) continue;
        //     if(v[j].first >= v[i].first && v[j].first <= v[i].second && v[j].second > mx && v[j].second > v[i].second) {
        //         mx = v[j].second;
        //         id = j;
        //     }
        // }

        if(v[i+1].first > v[i].second) continue;
        int L = i+1, R = i+1;

        int l=i+1, r=n-1, pos=i+1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(v[mid].first >= v[i].first && v[mid].first <= v[i].second) R = mid, l = mid + 1;
            else r = mid - 1;
        }

        pii res = tree.query(L, R);
        id = res.second;

        if(id != -1 && v[id].second > v[i].second) {
            up[i][0] = id;
            out[i]++;
            //cout << i << " -> " << id << '\n';
            graph[i].push_back(id);
            graph[id].push_back(i);
        }
    }

    for(int i=0; i<n; i++) {
        if(out[i] == 0) {
            up[i][0] = i;
            dfs(i, i);
        }
    }

    for(int i=0; i<n; i++) {
        int l=0, r=depth[i], J=n;

        while(l <= r) {
            int mid = (l + r) / 2;
            int u = i;

            for(int j=LOG-1; j>=0; j--)
                if(mid & (1 << j)) u = up[u][j];

            if(v[u].second >= m + v[i].first) {
                J = mid;
                r = mid - 1;
            } else l = mid + 1;
        }

        if(J != n) ans = min(ans, J + 1);
    }

    cout << (ans == 1e9 ? -1 : ans) << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:101:13: warning: unused variable 'mx' [-Wunused-variable]
  101 |         int mx=0, id=-1;
      |             ^~
Main.cpp:113:27: warning: unused variable 'pos' [-Wunused-variable]
  113 |         int l=i+1, r=n-1, pos=i+1;
      |                           ^~~

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