Submission #1264131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264131		goulthen	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	252 ms	77668 KiB

Main

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

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; ++i)
#define per(i,a,b) for (int i = a; i >= b; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define pb push_back

const int MAXN = 1e5 + 10;

struct Range {
	int l, r;
	Range(int x, int y) {
		l = x;
		r = y;
	}
	Range(int x) { l = r = x; }
	Range() {
		l = INT_MAX;
		r = INT_MIN;
	}
	Range operator|(Range a) { return Range(min(l, a.l), max(r, a.r)); }
	void operator|=(Range a) {
		l = min(l, a.l);
		r = max(r, a.r);
	}
};

struct Seg3{
	vector<Range> v;
	int c;
	void update(int x, Range y) {
		x += 1 << c;
		while (x) {
			v[x] |= y;
			x /= 2;
		}
	}
	Range calc(int x) { return v[x+(1<<c)]; }
	Range calc(int l, int r) {
		l += 1 << c;
		r += 1 << c;
		Range x;
		while (l<=r) {
			x |= v[l];
			x |= v[r];
			l = (l + 1)/2;
			r = (r - 1)/2;
		}
		return x;
	}
	Range calc(Range x) { return calc(x.l, x.r); }

	Seg3() {}
	Seg3(int n) {
		c = 0;
		while ((1 << c) < n) c++;
		v.resize(1 << c + 1);
	}
};
int n,m,k,q;
Range R[MAXN];
Seg3 seg[18];



int query(int s, int t) {
    int cnt = 0;
    Range p = Range(s);
    per(i, 17, 0) {
        Range q = seg[i].calc(p);
        if (!(q.l <= t && t <= q.r)) {
            p = q;
            cnt += 1 << i;
        }
    }
    if (cnt == (1 << 18) - 1) return -1;
    else return cnt + 1;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);

	cin >> n >> k >> m;

	rep(i,0,17) seg[i] = Seg3(n);
	rep(i,0,n-1) R[i] = Range(i);
	rep(i,1,m) {
		int a,b;cin >> a >> b;
		R[a-1] |= Range(b-1);
	}

	deque<pii> dq;

	rep(i,0,n-1) {
		while (!dq.empty() && dq.back().fi < R[i].r) dq.pop_back();
		dq.push_back({R[i].r,i+k-1});
		seg[0].update(i, Range(dq.front().fi));
		while (!dq.empty() && dq.front().se <= i) dq.pop_front();
	}
	dq.clear();
	per(i,n-1,0) {
		while(!dq.empty() && dq.back().fi > R[i].l) dq.pop_back();
		dq.push_back({R[i].l,i-k+1});
		seg[0].update(i, Range(dq.front().fi));
		while (!dq.empty() && dq.front().se >= i) dq.pop_front();
	}

	rep(i,1,17) {
		rep(j,0,n-1) {
			seg[i].update(j, seg[i-1].calc(seg[i-1].calc(j)));
		}
	}
	cin >> q;
	while (q--) {
		int u,v;cin >> u >> v;
		u--;v--;
		cout << query(u,v) << '\n';
	}
}

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