oj.uz

Submission #548292

# Submission time Handle Problem Language Result Execution time Memory
548292 2022-04-12T21:58:15 Z aryan12 Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 84 ms 40204 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 <= 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 left, 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 74 ms 38472 KB Output is correct
2 Correct 75 ms 38024 KB Output is correct
3 Correct 71 ms 38052 KB Output is correct
4 Correct 73 ms 38484 KB Output is correct
5 Correct 84 ms 40204 KB Output is correct
6 Correct 67 ms 36452 KB Output is correct
7 Incorrect 68 ms 37196 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 40080 KB Output is correct
2 Correct 76 ms 39436 KB Output is correct
3 Correct 75 ms 36700 KB Output is correct
4 Correct 77 ms 36304 KB Output is correct
5 Correct 72 ms 37604 KB Output is correct
6 Correct 66 ms 36812 KB Output is correct
7 Incorrect 69 ms 36444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 38472 KB Output is correct
2 Correct 75 ms 38024 KB Output is correct
3 Correct 71 ms 38052 KB Output is correct
4 Correct 73 ms 38484 KB Output is correct
5 Correct 84 ms 40204 KB Output is correct
6 Correct 67 ms 36452 KB Output is correct
7 Incorrect 68 ms 37196 KB Output isn't correct
8 Halted 0 ms 0 KB -