Submission #1056150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056150		anango	Fire (BOI24_fire)	C++17	100 / 100	1066 ms	270252 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;


const int K = 20;
int INF = 1LL<<60;

signed main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        //freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        //freopen("output.txt", "w", stdout);
    #endif
    #ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif //fast IO
    int n,m; cin >> n >> m;
    vector<pair<int,int>> segments;
    vector<int> coords;
    //coords.push_back(0); //0 to m-1
    map<int,int> rev;
    for (int i=0; i<n; i++) {
        int l,r; cin >> l >> r;
        if (l<r) {
            segments.push_back({l,r}); 
            coords.push_back(l); 
            coords.push_back(r);
            segments.push_back({m+l,m+r}); 
            coords.push_back(m+l); 
            coords.push_back(m+r);
        }
        else {
            segments.push_back({l,m+r}); 
            coords.push_back(l); 
            coords.push_back(m+r);
        }
    }
    int n0 = segments.size();
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()),coords.end());
    int k = coords.size();
    for (int i=0; i<k; i++) {
        rev[coords[i]] = i;
    }
    for (int i=0; i<n0; i++) {
        segments[i] = {rev[segments[i].first],rev[segments[i].second]};
    }
    vector<int> go(k,-1);
    multiset<int> ends;
    set<int> indices;
    sort(segments.begin(), segments.end());
    int pointer = 0;
    int lpointer = 0;
    for (int i=0; i<k; i++) {
        while (pointer<n0 && segments[pointer].first==i) {
            indices.insert(pointer);
            ends.insert(segments[pointer].second);
            pointer++;
        }
        if (!ends.size()) {
            go[i] = -1;
        }
        else {
            go[i] = *ends.rbegin();
        }
        while (lpointer<n0 && segments[lpointer].second==i) {
            indices.erase(lpointer);
            ends.erase(ends.find(segments[lpointer].second));
            lpointer++;
        }
    }
    for (int i=0; i<k; i++) {
        //cout << i <<" " << coords[i] <<" " << go[i] << " " << coords[go[i]] << endl;
    }
    vector<vector<int>> lift(k,vector<int>(K,-1));
    for (int i=0; i<k; i++) {
        lift[i][0] = go[i];
    }
    for (int p=1; p<K; p++) {
        for (int i=0; i<k; i++) {
            lift[i][p] = lift[lift[i][p-1]][p-1];
        }
    }
    int mians = INF;
    for (int i=0; i<k; i++) {
        int cur = i;
        int ct = 0;
        for (int p=K-1; p>=0; p--) {
            if (coords[lift[cur][p]]<coords[i]+m) {
                cur = lift[cur][p];
                ct+=1<<p;
            }
        }
        int p = 0;
        if (coords[lift[cur][p]]<=coords[i]+m) {
            cur = lift[cur][p];
            ct++;
        }
        if (coords[cur]>=coords[i]+m) {
            mians=min(mians,ct);
        }
    }
    if (mians<INF) cout << mians << endl;
    else cout << -1 << endl;



    
}

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