oj.uz

Submission #980094

# Submission time Handle Problem Language Result Execution time Memory
980094 2024-05-11T23:25:22 Z OAleksa Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 20692 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e5 + 69;
const int K = 18;
vector<pair<int, int>> g[2 * N];
int n, q, l[N], r[N];
int cl[N], cr[N];
int ll[N][K], rr[N][K];
//desno sa najvecom granicom i levo sa najvecom granicom
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
	while (tt--) {		
		cin >> n >> q;
		vector<int> xs;
		for (int i = 1;i <= n;i++) {
			cin >> l[i] >> r[i];
			xs.push_back(l[i]);
			xs.push_back(r[i]);
		}
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		for (int i = 1;i <= n;i++) {
			cl[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin() + 1;
			cr[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin() + 1;
			g[cl[i]].push_back({0, i});
			g[cr[i]].push_back({1, i});
		}
		set<pair<int, int>> st;
		for (int i = 1;i <= 2 * n;i++) {
			sort(g[i].begin(), g[i].end());
			for (auto j : g[i]) {
				//samo sto se otvaraju
				if (j.f == 0) {	
					st.insert({cr[j.s], j.s});
				}
				else {
					rr[j.s][0] = (*st.rbegin()).s;
					st.erase({cr[j.s], j.s});
				}
			}
		}
		for (int j = 1;j < K;j++) {
			for (int i = 1;i <= n;i++) {
				rr[i][j] = rr[rr[i][j - 1]][j - 1];
			}
		}
		while (q--) {
			int x, y;
			cin >> x >> y;
			if (r[x] <= r[y]) {
				//desno
				int ans = 0, ok = 0;
				while (x != y && ans < n + 10) {
					ans += 1;
					if (r[x] > r[y]) {
						ok = 1;
						break;
					}
					x = rr[x][0];
				}
				ok |= (ans > n);
				if (!ok)
					cout << ans << '\n';
				else
					cout << "impossible\n";
			}
			else 
				cout << "impossible\n";
		}
	}
  return 0; 
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Execution timed out 1571 ms 20692 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Incorrect 2 ms 8284 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Incorrect 2 ms 8284 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Incorrect 2 ms 8284 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1539 ms 20628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Execution timed out 1571 ms 20692 KB Time limit exceeded
3 Halted 0 ms 0 KB -