Submission #1310602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310602		harryleee	Fire (BOI24_fire)	C++20	0 / 100	2 ms	1860 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5;
int n, m, nxt[maxn + 1], ttime;
int ans = maxn + 5;
int vis[maxn + 1];
vector<int> value;
pair<int, int> a[maxn + 1];

struct SEGMENT_TREE{
    vector<pair<int, int>> st;

    inline SEGMENT_TREE(int n){
        st.resize(4 * n + 4, {0, 0});
    }
    inline void update(int ind, int l, int r, int pos, int val, int id){
        if (l == r){
            st[ind] = max(st[ind], make_pair(val, id));
            return;
        }
        int mid = (l + r) >> 1;
        if (mid >= pos) update(ind << 1, l, mid, pos, val, id);
        else update(ind << 1 | 1, mid + 1, r, pos, val, id);
        st[ind] = max(st[ind << 1], st[ind << 1 | 1]);
        return;
    }
    inline pair<int, int> get(int ind, int l, int r, int lb, int rb){
        if (lb > rb) return {0, 0};
        if (l >= lb && r <= rb) return st[ind];
        int mid = (l + r) >> 1;
        pair<int, int> res = {0, 0};
        if (mid >= lb) res = max(res, get(ind << 1, l, mid, lb, rb));
        if (mid < rb) res = max(res, get(ind << 1 | 1, mid + 1, r, lb, rb));
        return res;
    }
};

inline int DFS(int u){
    vis[u] = ttime;
    int v = nxt[u];
    if (v == -1)
        return maxn + 5;
    if (vis[v] == 0)
        return DFS(v);
    if (vis[v] == ttime){
        int start = v, res = 0;
        while(true){
            res++;
            if (start == u) 
                break;
            start = nxt[start];
        }
        return res;
    }
    return 0;
}   

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(vis, 0, sizeof(vis));

    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].first >> a[i].second;
        value.push_back(a[i].first);
        value.push_back(a[i].second);
    }

    sort(value.begin(), value.end());
    value.erase(unique(value.begin(), value.end()), value.end());
    SEGMENT_TREE seg(value.size());

    for (int i = 1; i <= n; ++i){
        int pos = lower_bound(value.begin(), value.end(), a[i].first) - value.begin();
        int val = a[i].second;
        if (a[i].second < a[i].first) 
            val += m;
        // cout << pos << ' ' << val << '\n';
        seg.update(1, 0, value.size() - 1, pos, val, i);
    }

    for (int i = 1; i <= n; ++i){
        int it1 = lower_bound(value.begin(), value.end(), a[i].first) - value.begin();
        int it2 = lower_bound(value.begin(), value.end(), a[i].second) - value.begin();
        pair<int, int> opt = {0, 0};
        if (a[i].second < a[i].first)
            opt = max(seg.get(1, 0, value.size() - 1, it1 + 1, value.size() - 1), seg.get(1, 0, value.size() - 1, 0, it2));
        else
            opt = seg.get(1, 0, value.size() - 1, it1 + 1, it2);
        if (opt.first <= a[i].second)
            nxt[i] = -1;
        else
            nxt[i] = opt.second;
        // cout << opt.first << ' ' << opt.second << '\n';
    }

    for (int i = 1; i <= n; ++i) if (vis[i] == 0){
        ++ttime;
        ans = min(ans, DFS(i));
    }


    if (ans == maxn + 5) ans = -1;
    cout << ans;
    return 0;
}

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