oj.uz

Submission #580213

# Submission time Handle Problem Language Result Execution time Memory
580213 2022-06-20T17:59:06 Z penguinhacker Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 10036 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, ls[2*mxN], rs[2*mxN], ans[mxN];
ar<int, 2> segs[mxN];
vector<int> d;
vector<ar<int, 3>> qry[2*mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i) {
		cin >> segs[i][0] >> segs[i][1];
		d.push_back(segs[i][0]);
		d.push_back(segs[i][1]);
	}
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	memset(ls, -1, sizeof(ls));
	for (int i=0; i<n; ++i) {
		segs[i][0]=lower_bound(d.begin(), d.end(), segs[i][0])-d.begin();
		segs[i][1]=lower_bound(d.begin(), d.end(), segs[i][1])-d.begin();
		//cout << "seg  " <<  segs[i][0] << " " << segs[i][1] << endl;
		if (ls[segs[i][1]]==-1||segs[i][0]<ls[segs[i][1]])
			ls[segs[i][1]]=segs[i][0];
	}
	for (int i=0; i<q; ++i) {
		int a, b;
		cin >> a >> b, --a, --b;
		ans[i]=-1;
		if (segs[a][1]<segs[b][1])
			qry[segs[b][1]].push_back({segs[a][1], segs[b][0], i});
		if (segs[a][1]==segs[b][1])
			ans[i]=a!=b;
	}
	iota(rs, rs+d.size(), 0);
	for (int i=0; i<d.size(); ++i) {
		if (ls[i]!=-1)
			for (int j=ls[i]; j<=i; ++j)
				rs[j]=i;
		//for (int j=0; j<=i; ++j)
		//	cout << rs[j] << " ";
		//cout << endl;
		for (auto [s, bound, ind] : qry[i]) {
			int cur=0;
			while(rs[s]<i&&rs[s]!=s)
				++cur, s=rs[s];
			if (rs[s]!=i)
				continue;
			++cur;
			cur+=s<bound;
			ans[ind]=cur;
		}
	}
	for (int i=0; i<q; ++i) {
		if (ans[i]==-1)
			cout << "impossible\n";
		else
			cout << ans[i] << "\n";
	}
	return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
events.cpp:49:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   for (auto [s, bound, ind] : qry[i]) {
      |             ^

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5764 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 4 ms 5848 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5764 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 4 ms 5848 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 3 ms 5844 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct
16 Correct 4 ms 5844 KB Output is correct
17 Correct 4 ms 5844 KB Output is correct
18 Correct 4 ms 5844 KB Output is correct
19 Correct 357 ms 8352 KB Output is correct
20 Correct 1079 ms 8356 KB Output is correct
21 Correct 212 ms 7996 KB Output is correct
22 Correct 28 ms 7952 KB Output is correct
23 Correct 35 ms 7888 KB Output is correct
24 Correct 38 ms 7936 KB Output is correct
25 Correct 47 ms 8280 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5764 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 4 ms 5848 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 4 ms 5716 KB Output is correct
11 Correct 4 ms 5716 KB Output is correct
12 Correct 4 ms 5832 KB Output is correct
13 Correct 4 ms 5844 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 4 ms 5820 KB Output is correct
16 Correct 4 ms 5844 KB Output is correct
17 Correct 4 ms 5832 KB Output is correct
18 Correct 4 ms 5716 KB Output is correct
19 Correct 91 ms 9292 KB Output is correct
20 Correct 63 ms 8080 KB Output is correct
21 Correct 362 ms 7864 KB Output is correct
22 Correct 59 ms 7996 KB Output is correct
23 Execution timed out 1586 ms 8508 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1588 ms 10036 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 5716 KB Output is correct
2 Execution timed out 1596 ms 10000 KB Time limit exceeded
3 Halted 0 ms 0 KB -