Submission #1071808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071808		_rain_	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	737 ms	89760 KiB

Main

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

#define left abcs
#define right cbdx

void SETIO(string name = ""){
    if (name=="") return;
    freopen((name+".inp").c_str(),"r",stdin);
//    freopen((name+".out").c_str(),"w",stdout);
    return;
}
#define MASK(x) ((ll)(1)<<(x))
#define BIT(mask,x) (((mask)>>(x))&(1))

const int maxn = 1e5;
const int maxlog = 17;
int golt[maxn+2][maxlog+2] , gort[maxn+2][maxlog+2] , LOG[maxn+2];
int le[maxn+2][maxlog+2] , ri[maxn+2][maxlog+2];
int n , k , m ;

int queryL(int l , int r){
    int x = LOG[r - l + 1];
    return min(golt[l][x] , golt[r - MASK(x) + 1][x]);
}
int queryR(int l , int r){
    int x = LOG[r- l + 1];
    return max(gort[l][x] , gort[r - MASK(x) + 1][x]);
}

class segment_tree{
    public:
        vector<int> stl , str;

        void build(int id , int l , int r , int k){
            if (l==r) {
                stl[id] = le[l][k];
                str[id] = ri[l][k];
            }
            else {
                int m = l+r>>1;
                build(id*2,l,m,k);
                build(id*2+1,m+1,r,k);
                stl[id] = min(stl[id * 2] , stl[id * 2 + 1]);
                str[id] = max(str[id * 2] , str[id * 2 + 1]);
                return;
            }
        }
        void init(int n , int k){
            stl.assign(n*4+2,0);
            str.assign(n*4+2,0);
            build(1,1,n,k);
            return;
        }
        int getMin(int id , int l , int r , int u , int v){
            if (l > v || r < u) return n+1;
            if (u <= l && r <= v) return stl[id];
            int m = l + r >> 1;
            return min(getMin(id*2,l,m,u,v) , getMin(id*2+1,m+1,r,u,v));
        }
        int getMax(int id , int l , int r , int u , int v){
            if (l > v || r < u) return 0;
            if (u <= l && r <= v) return str[id];
            int m = l + r >> 1;
            return max(getMax(id*2,l,m,u,v) , getMax(id*2+1,m+1,r,u,v));
        }
} ;
segment_tree st[maxlog+2];

int ask(int s , int t){
    int l = s , r = s , res = 0;
    for (int j = maxlog; j >= 0; --j){
        int L = st[j].getMin(1,1,n,l,r);
        int R = st[j].getMax(1,1,n,l,r);
        if (L <= t && t <= R) continue;
        l = L , r = R;
        res += MASK(j);
    }
    if (res > n) return -1;
    return res + 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    SETIO("");

    cin >> n >> k >> m;
    for (int i = 2; i <= n; ++i) LOG[i] = LOG[i / 2] + 1;
    for (int i = 0; i <= n + 1; ++i) golt[i][0] = n + 1 , gort[i][0] = 0;

    for (int i = 1; i <= m; ++i){
        int s ,t; cin >> s >> t;
        if (s > t) golt[s][0] = min(golt[s][0] , t);
            else gort[s][0] = max(gort[s][0] , t);
        if (fixbug){
            cout << "( DEBUG )\n";
            cout << s << "->" << t << '\n';
        }
    }
    //... BUILDING RMQ
        for (int j = 1; j <= maxlog; ++j){
            for (int i = 1; i + MASK(j) - 1 <= n; ++i){
                golt[i][j] = min(golt[i][j - 1] , golt[i + MASK(j-1)][j - 1]);
                gort[i][j] = max(gort[i][j - 1] , gort[i + MASK(j-1)][j - 1]);
            }
        }
    //...;

    for (int i = 1; i <= n; ++i){
        le[i][0] = min(i,queryL(i , min(i + k - 1 , n)));
        ri[i][0] = max(i,queryR(max(i - k + 1 , 1) ,  i));
    }
    st[0].init(n,0);
    for (int j = 1; j <= maxlog; ++j){
        for (int i = 1; i <= n; ++i){
            le[i][j] = st[j - 1].getMin(1,1,n,le[i][j - 1] , ri[i][j - 1]);
            ri[i][j] = st[j - 1].getMax(1,1,n,le[i][j - 1] , ri[i][j - 1]);
        }
        st[j].init(n,j);
    }
    if (fixbug){
        cout << "( DEBUG )\n";
        for (int j = 0; j <= maxlog; ++j) {
            cout << "FOR THE J : " << j << '\n';
            for (int i = 1; i <= n; ++i)
                cout << le[i][j] << ' ' << ri[i][j] << '\n';
        }
    }
    int q; cin >> q;
    while(q--) {
        int s , t; cin >> s >> t;
        cout << ask(s,t) << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segment_tree::build(int, int, int, int)':
Main.cpp:43:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |                 int m = l+r>>1;
      |                         ~^~
Main.cpp: In member function 'int segment_tree::getMin(int, int, int, int, int)':
Main.cpp:60:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |             int m = l + r >> 1;
      |                     ~~^~~
Main.cpp: In member function 'int segment_tree::getMax(int, int, int, int, int)':
Main.cpp:66:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |             int m = l + r >> 1;
      |                     ~~^~~
Main.cpp: In function 'void SETIO(std::string)':
Main.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen((name+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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