Submission #1170671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170671		hoa208	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	715 ms	298716 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
#define t_test int t;cin >> t;while(t--)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
inline  void adm(ll &x){if(x>=mod)x%=mod;else if(x<0)x+=mod;}
//--------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, k, m;
int q;
int L[N][18], R[N][18];
int inL[N][18], inR[N][18];
int ans_L[18][N][18], ans_R[18][N][18];
multiset<int> st;
vector<int> event_R[N], event_L[N];
void hbmt() {
    cin >> n >> k;
    cin >> m;
    FOR(i, 1, m) {
        int a, b;
        cin >> a >> b;
        if(a == b) while(1);
        if(a < b) {
            int c = a + k - 1;
            c = min(c, b);
            event_R[a].push_back(b);
            event_R[c + 1].push_back(-b);
        }
        else { 
            int c = a - k + 1;
            c = max(c, b);
            event_L[a].push_back(b);
            event_L[c - 1].push_back(-b);
        }
    }
    memset(R, -1, sizeof R);
    memset(L, -1, sizeof L);
    FOR(i, 1, n) {
        for(auto w : event_R[i]) {
            if(w < 0) st.erase(st.find(-w));
            else st.insert(w);
        }
        R[i][0] = (st.empty() ? i : *st.rbegin());
    }
    st.clear();
    FORD(i, n, 1) {
        for(auto w : event_L[i]) {
            if(w < 0) st.erase(st.find(-w));
            else st.insert(w);
        }
        L[i][0] = (st.empty() ? i : *st.begin());
    }
    FOR(j, 1, 17) {
        FOR(i, 1, n) {
            inR[i][0] = R[i][j - 1];
            inL[i][0] = L[i][j - 1];
        }
        FOR(u, 1, 17) {
            for(int i = 1; i + (1 << u) - 1 <= n; i++) {
                inL[i][u] = min(inL[i][u - 1], inL[i + (1 << (u - 1))][u - 1]);
                inR[i][u] = max(inR[i][u - 1], inR[i + (1 << (u - 1))][u - 1]);
            }
        }
        for(int i = 1; i <= n; i++) {
            int l = L[i][j - 1];
            int r = R[i][j - 1];
            int c = __lg(r - l + 1); 
            L[i][j] = min(inL[l][c], inL[r - (1 << c) + 1][c]);
            R[i][j] = max(inR[l][c], inR[r - (1 << c) + 1][c]);
        }
    }
    memset(ans_R, -1, sizeof ans_R);
    memset(ans_L, -1, sizeof ans_L);
    FOR(j, 0, 17) {
        FOR(i, 1, n) {
            ans_R[j][i][0] = R[i][j]; 
           ans_L[j][i][0] = L[i][j];
        }
        FOR(u, 1, 17) {
            for(int i = 1; i + (1 << u) - 1 <= n; i++) {
                ans_R[j][i][u] = max(ans_R[j][i][u - 1], ans_R[j][i + (1 << (u - 1))][u - 1]);
                ans_L[j][i][u] = min(ans_L[j][i][u - 1], ans_L[j][i + (1 << (u - 1))][u - 1]);
            }
        }
    }
    cin >>  q;
    FOR(i, 1, q) {
        int x, y;
        cin >> x >> y;
        int u = x, v = x;
        int res = 0;
        FORD(j, 17, 0) {
            int l = u, r = v;
            int c = __lg(r - l + 1);
            int _u = min(ans_L[j][l][c], ans_L[j][r - (1 << c) + 1][c]);
            int _v = max(ans_R[j][l][c], ans_R[j][r - (1 << c) + 1][c]);
            if(_u != -1 && _v != -1 && (_v < y || _u > y)) {
                u = _u;
                v = _v;
                res += (1 << j);
            }
        }
        res++;
        if(res == (1 << 18)) cout << -1 << '\n';
        else
        cout << res << '\n';
    }
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    if(fopen("hbmt.inp", "r")) {
        freopen("hbmt.inp", "r", stdin);
        freopen("hbmt.out", "w", stdout);
    }
    
    // t_test 
    hbmt();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen("hbmt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen("hbmt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13