oj.uz

Submission #527723

# Submission time Handle Problem Language Result Execution time Memory
527723 2022-02-18T05:34:35 Z 8e7 Railway Trip 2 (JOI22_ho_t4) C++17
46 / 100
 312 ms 40000 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
pii ed[200005];
int rig[maxn], lef[maxn];
vector<pii> el[maxn], er[maxn];

struct segtree{
	int type = 0;
	pii seg[4*maxn];
	void pull(int cur) {
		if (type) seg[cur] = max(seg[cur*2], seg[cur*2+1]);
		else seg[cur] = min(seg[cur*2], seg[cur*2+1]);
	}
	void init(int cur, int l, int r){
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = {(type ? 0 : inf), l}; 
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
		pull(cur);	
	}
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = {val, l};
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind, val);
		else modify(cur*2+1, m, r, ind, val);
		pull(cur);
	}
	pii query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return type ? make_pair(0, 0) : make_pair(inf, 0);
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		pii le = query(cur*2, l, m, ql, qr), ri = query(cur*2+1, m, r, ql, qr);
		return type ? max(le, ri) : min(le, ri);
	}
} sl, sr;

int tol[17][maxn], tor[17][maxn];

vector<int> adj[maxn];
int dis[maxn];
int main() {
	io
	int n, k, m;
	cin >> n >> k >> m;
	for (int i = 0;i < m;i++) {
		cin >> ed[i].ff >> ed[i].ss;
		if (ed[i].ss > ed[i].ff) {
			er[min(ed[i].ss-1, ed[i].ff + k - 1)].push_back({ed[i].ss, 1});
			er[ed[i].ff - 1].push_back({ed[i].ss, -1});
		} else {
			el[max(ed[i].ss+1, ed[i].ff - k + 1)].push_back({ed[i].ss, 1});
			el[ed[i].ff + 1].push_back({ed[i].ss, -1});
		}
	}
	multiset<int> se;
	for (int i = 1;i <= n;i++) {
		for (auto p:el[i]) {
			if (p.ss == 1) se.insert(p.ff);	
			else se.erase(se.find(p.ff));
		}
		lef[i] = (se.size() ? *se.begin() : i);
	}
	se.clear();
	for (int i = n;i >= 1;i--) {
		for (auto p:er[i]) {
			if (p.ss == 1) se.insert(p.ff);	
			else se.erase(se.find(p.ff));
		}
		rig[i] = (se.size() ? *prev(se.end()) : i);
	}

	sl.init(1, 1, n+1);
	sr.type = 1;
	sr.init(1, 1, n+1);
	for (int i = 1;i <= n;i++) {
		sl.modify(1, 1, n+1, i, lef[i]);
		sr.modify(1, 1, n+1, i, rig[i]);
	}
	for (int i = 1;i <= n;i++) {
		pii nxt = sr.query(1, 1, n+1, i+1, rig[i]+1);	
		tor[0][i] = nxt.ss;
		adj[i].push_back(nxt.ss);

		nxt = sl.query(1, 1, n+1, i+1, rig[i]+1);	
		adj[i].push_back(nxt.ss);

		nxt = sl.query(1, 1, n+1, lef[i], i);	
		tol[0][i] = nxt.ss;
		adj[i].push_back(nxt.ss);

		nxt = sr.query(1, 1, n+1, lef[i], i);	
		adj[i].push_back(nxt.ss);
	}
	pary(lef + 1, lef + n + 1);	
	pary(rig + 1, rig + n + 1);

	lef[0] = 0;
	rig[0] = n+1;
	pary(tol[0] + 1, tol[0] + n + 1);
	pary(tor[0] + 1, tor[0] + n + 1);

	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) {
			tol[i][j] = tol[i-1][tol[i-1][j]];
			tor[i][j] = tor[i-1][tor[i-1][j]];
		}
	}
	//brute force
	for (int i = 1;i <= n;i++) {
		adj[i].push_back(tol[0][i]);
		adj[i].push_back(tor[0][i]);
	}
	int q;
	cin >> q;
	if (q == 1 || n <= 2) {
		while (q--) {
			int s, t;
			cin >> s >> t;
			for (int i = 1;i <= n;i++) dis[i] = inf;
			dis[s] = 0;
			queue<int> que;
			que.push(s);	
			int ans = inf;
			while (que.size()) {
				int cur = que.front();que.pop();
				if ((lef[cur] <= t && t <= cur) || (rig[cur] >= t && t > cur)) {
					ans = dis[cur];
					break;
				}
				for (int v:adj[cur]) {
					if (dis[v] > dis[cur] + 1) {
						dis[v] = dis[cur] + 1;
						que.push(v);
					}
				}
			}
			cout << (ans == inf ? -1 : ans+1) << "\n";
		}
	} else {
		while (q--) {
			int s, t;
			cin >> s >> t;
			int ans = 0;
			if (s < t) {
				for (int i = 16;i >= 0;i--) {
					if (rig[tor[i][s]] < t) {
						s = tor[i][s];
						ans += 1<<i;
					}
				}
				//debug(s, rig[s]);
				if (rig[s] >= t) ans++;
				else if (rig[tor[0][s]] >= t && tor[0][s] != 0) ans += 2;
				else ans = -1;
			} else {
				for (int i = 16;i >= 0;i--) {
					if (lef[tol[i][s]] > t) {
						s = tol[i][s];
						ans += 1<<i;
					}
				}
				if (lef[s] < t) ans = -1;
				else ans++;
			}
			cout << ans << "\n";
			//debug();
		}
	}
	
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
Main.cpp:121:2: note: in expansion of macro 'pary'
  121 |  pary(lef + 1, lef + n + 1);
      |  ^~~~
Main.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
Main.cpp:122:2: note: in expansion of macro 'pary'
  122 |  pary(rig + 1, rig + n + 1);
      |  ^~~~
Main.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
Main.cpp:126:2: note: in expansion of macro 'pary'
  126 |  pary(tol[0] + 1, tol[0] + n + 1);
      |  ^~~~
Main.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
Main.cpp:127:2: note: in expansion of macro 'pary'
  127 |  pary(tor[0] + 1, tor[0] + n + 1);
      |  ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 34200 KB Output is correct
2 Correct 149 ms 34148 KB Output is correct
3 Correct 168 ms 34500 KB Output is correct
4 Correct 168 ms 34340 KB Output is correct
5 Correct 297 ms 39236 KB Output is correct
6 Correct 190 ms 38472 KB Output is correct
7 Correct 223 ms 40000 KB Output is correct
8 Correct 227 ms 35612 KB Output is correct
9 Correct 201 ms 35680 KB Output is correct
10 Correct 254 ms 39184 KB Output is correct
11 Correct 250 ms 39236 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 35316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 38008 KB Output is correct
2 Correct 184 ms 34500 KB Output is correct
3 Correct 180 ms 32516 KB Output is correct
4 Correct 156 ms 31340 KB Output is correct
5 Correct 135 ms 30812 KB Output is correct
6 Correct 163 ms 30540 KB Output is correct
7 Correct 170 ms 35072 KB Output is correct
8 Correct 4 ms 7628 KB Output is correct
9 Correct 7 ms 8132 KB Output is correct
10 Correct 275 ms 38112 KB Output is correct
11 Correct 274 ms 37956 KB Output is correct
12 Correct 312 ms 37796 KB Output is correct
13 Correct 283 ms 37828 KB Output is correct
14 Correct 4 ms 7628 KB Output is correct
15 Correct 7 ms 8140 KB Output is correct
16 Correct 240 ms 38236 KB Output is correct
17 Correct 241 ms 38096 KB Output is correct
18 Correct 249 ms 38104 KB Output is correct
19 Correct 242 ms 38128 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7628 KB Output isn't correct
2 Halted 0 ms 0 KB -