Submission #1304593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304593		kirakosyan	Fire (BOI24_fire)	C++20	40 / 100	25 ms	2004 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>


using namespace std;
using ll = long long;
ll mod = 998244353;
ll gcd(ll a, ll b) {
    if (b == 0)return a;
    else return gcd(b, a % b);
}
vector<pair<int, int>>v;
vector<pair<int, int>>seg;
void build(int l, int r, int u) {
    if (l == r) {
        seg[u] = { v[l].second,l };
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * u + 1);
    build(mid+1, r, 2 * u + 2);
    seg[u] = max(seg[2 * u + 1], seg[2 * u + 2]);

}
pair<int,int> get(int l, int r, int u,int lx,int rx) {
    if (l >=lx&&r<=rx) {
        return seg[u];
    }
    if (l > rx || r < lx) {
        return { -1,-1 };
    }
    int mid = (l + r) / 2;
    return max({ get(l, mid, 2 * u + 1,lx,rx),get(mid + 1, r, 2 * u + 2,lx,rx) });
    
}
void solve() {
    int n, m; cin >> n >> m;
    v=vector<pair<int,int>>(n);
    int f = 1;
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
        if (v[i].first > v[i].second) {
            v[i].second += m;
        }
        if (v[i].second - v[i].first + 1 >= m)f = 0;
    }
    if (f == 0) {
        cout << 1 << endl;
        return;
    }
    sort(v.begin(), v.end());
    int s = 1;
    while (s < n)s <<= 1;
    seg = vector<pair<int, int>>(2 * s - 1);
    build(0, s - 1, 0);
    vector<vector<int>>up(n, vector<int>(22));
    for (int i = 0; i < n; i++) {
        pair<int, int>p;
        p.first = v[i].second+1;
        p.second = -1;
        int ind = lower_bound(v.begin(), v.end(), p) - v.begin() - 1;
        int bro = get(0, s - 1, 0, i, ind).second;
        up[i][0] = bro;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 1; j <= 20; j++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++) {
        int l = -1, r = n + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2, x = i;
            for (int j = 20; j >= 0; j--) {
                if (mid & (1 << j)) {
                    x = up[x][j];
                }
            }
            if (v[x].second - v[i].first + 1 >= m) {
                ans = min(ans, mid);
                r = mid;

            }
            else l = mid;

        }
    }
    if (ans == 1e9)cout << -1 << endl;
    else cout << ans+1 << endl;

}

signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

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