Submission #1262460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262460		vlomaczk	Railway Trip 2 (JOI22_ho_t4)	C++20	27 / 100	93 ms	37696 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int base = 1<<17;

struct min_left {
	vector<int> t;
	void construct() { t.assign(2*base, INT_MAX); }

	void update(int a, int b, int val) {
		if(a==b) {
			t[a+base] = min(t[a+base], val);
			return;
		}
		a += base-1;
		b += base+1;
		while(a/2 != b/2) {
			if(a%2==0) t[a+1] = min(t[a+1], val);
			if(b%2==1) t[b-1] = min(t[b-1], val);
			a/=2; b/=2;
		}
	}

	int query(int x) {
		int ans = INT_MAX;
		x += base;
		while(x > 0) {
			ans = min(ans, t[x]);
			x/=2;
		}
		return ans;
	}
};

struct max_right {
	vector<int> t;
	void construct() { t.assign(2*base, 0); }

	void update(int a, int b, int val) {
		if(a==b) {
			t[a+base] = max(t[a+base], val);
			return;
		}
		a += base-1;
		b += base+1;
		while(a/2 != b/2) {
			if(a%2==0) t[a+1] = max(t[a+1], val);
			if(b%2==1) t[b-1] = max(t[b-1], val);
			a/=2; b/=2;
		}
	}

	int query(int x) {
		int ans = 0;
		x += base;
		while(x > 0) {
			ans = max(ans, t[x]);
			x/=2;
		}
		return ans;
	}
};

struct sparse_table_max {
    vector<vector<pair<int,int>>> st;
    vector<int> log2;

    void construct(const vector<int> v) {
        int n = v.size();
        log2.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) 
            log2[i] = log2[i/2] + 1;

        int K = log2[n] + 1;
        st.assign(n, vector<pair<int,int>>(K));

        for (int i = 0; i < n; i++)
            st[i][0] = {v[i], i};

        for (int j = 1; j < K; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                pair<int,int> left = st[i][j-1];
                pair<int,int> right = st[i + (1 << (j-1))][j-1];
                if (left.first >= right.first)
                    st[i][j] = left;
                else
                    st[i][j] = right;
            }
        }
    }

    pair<int,int> query(int a, int b) {
        int j = log2[b - a + 1];
        pair<int,int> left = st[a][j];
        pair<int,int> right = st[b - (1 << j) + 1][j];
        if (left.first >= right.first) return left;
        return right;
    }
};

struct sparse_table_min {
	sparse_table_max stm;

	void construct(vector<int> v) {
		for(auto &x : v) x*=-1;
		stm.construct(v);
	}

	pair<int, int> query(int a, int b) {
		pair<int, int> x = stm.query(a, b);
		x.first*=-1;
		return x;
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n, k;
	cin >> n >> k;
	min_left ml; ml.construct();
	max_right mr; mr.construct();
	for(int i=1; i<=n; ++i) {
		mr.update(i, i, i);
		ml.update(i, i, i);
	}
	int m;
	cin >> m;
	for(int i=0; i<m; ++i) {
		ll a, b;
		cin >> a >> b;
		if(a<b) {
			mr.update(a, min(a+k-1, b-1), b);
		} else {
			ml.update(max(a-k+1, b+1), a, b);
		}
	}
	vector<int> vml(n+1), vmr(n+1);
	for(int i=1; i<=n; ++i) {
		vml[i] = ml.query(i);
		vmr[i] = mr.query(i);
	}
	sparse_table_max stmax;
	sparse_table_min stmin;
	stmax.construct(vmr);
	stmin.construct(vml);
	//for(int i=1; i<=n; ++i) cout << vmr[i] << " "; cout << "\n";
	//for(int i=1; i<=n; ++i) cout << vml[i] << " "; cout << "\n";
	ll q;
	cin >> q;
	if(n*q <= 4'000'000) {
		while(q--) {
			int a, b;
			cin >> a >> b;
			int ans = 0;
			pair<int, int> curr = {a, a};
			pair<int, int> prev = {-1, -1};
			while(1) {
				if(curr.first == prev.first && curr.second == prev.second) break;
				if(curr.first <= b && b <= curr.second) break;
				prev = curr;
				curr.second = stmax.query(prev.first, prev.second).first;
				curr.first = stmin.query(prev.first, prev.second).first;
				ans++;
			}
			if(curr.first <= b && b <= curr.second) cout << ans << "\n";
			else cout << "-1\n";
		}
	} else {
		
	}

	return 0;
}

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