oj.uz

Submission #548293

# Submission time Handle Problem Language Result Execution time Memory
548293 2022-04-12T22:00:42 Z aryan12 Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 94 ms 36500 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
int DP[20][N];

void Solve() 
{
	int n;
	cin >> n;
	vector<int> max_left(n + 1, -1);
	vector<int> l(n + 1), r(n + 1);
	multiset<pair<int, int> > s;
	for(int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	int left = n + 1;
	for(int right = n; right > 0; right--)
	{
		while(left > 1)
		{
			s.insert(make_pair(l[left - 1], r[left - 1]));
			auto idx = s.lower_bound(make_pair(l[left - 1], r[left - 1]));
			// if(idx == s.begin())
			// {
			// 	cout << "in the beginning\n";
			// }
			// if(next(idx) == s.end())
			// {
			// 	cout << "in the end\n";
			// }
			if(idx != s.begin() && prev(idx)->second >= l[left - 1])
			{
				s.erase(make_pair(l[left - 1], r[left - 1]));
				break;
			}
			if(next(idx) != s.end() && next(idx)->first <= r[left - 1])
			{
				s.erase(make_pair(l[left - 1], r[left - 1]));
				break;
			}
			left--;
		}
		max_left[right] = left - 1;
		s.erase(make_pair(l[right], r[right]));
	}

	for(int i = 1; i <= n; i++)
	{
		// cout << max_left[i] << " ";
		DP[0][i] = max_left[i];
	}
	// cout << "\n";
	for(int i = 1; i < 20; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(DP[i - 1][j] == 0)
			{
				DP[i][j] = 0;
			}
			else
			{
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
			}
		}
	}
	int queries;
	cin >> queries;
	while(queries--)
	{
		int right;
		cin >> left >> right;
		int ans = 0;
		int cur_idx = right;
		for(int i = 19; i >= 0; i--)
		{
			if(DP[i][cur_idx] >= left)
			{
				cur_idx = DP[i][cur_idx];
				ans += (1 << i);
			}
		}
		cout << ans + 1 << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 34892 KB Output is correct
2 Correct 70 ms 34496 KB Output is correct
3 Correct 77 ms 34624 KB Output is correct
4 Correct 75 ms 34980 KB Output is correct
5 Correct 79 ms 36500 KB Output is correct
6 Correct 71 ms 33252 KB Output is correct
7 Incorrect 94 ms 33736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1492 KB Output is correct
2 Correct 4 ms 1344 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 4 ms 1428 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Incorrect 4 ms 1364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1492 KB Output is correct
2 Correct 4 ms 1344 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 4 ms 1428 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Incorrect 4 ms 1364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 36452 KB Output is correct
2 Correct 81 ms 35776 KB Output is correct
3 Correct 77 ms 33388 KB Output is correct
4 Correct 74 ms 33028 KB Output is correct
5 Correct 74 ms 34144 KB Output is correct
6 Correct 69 ms 33412 KB Output is correct
7 Incorrect 68 ms 33196 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 34892 KB Output is correct
2 Correct 70 ms 34496 KB Output is correct
3 Correct 77 ms 34624 KB Output is correct
4 Correct 75 ms 34980 KB Output is correct
5 Correct 79 ms 36500 KB Output is correct
6 Correct 71 ms 33252 KB Output is correct
7 Incorrect 94 ms 33736 KB Output isn't correct
8 Halted 0 ms 0 KB -