oj.uz

답안 #548279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548279 2022-04-12T20:54:27 Z aryan12 Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 97 ms 40296 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);
	set<pair<int, int> > s;
	for(int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	int left = n;
	for(int right = n; right > 0; right--)
	{
		while(left > 0)
		{
			auto idx = s.lower_bound(make_pair(l[left], r[left]));
			if(idx == s.end())
			{
				s.insert(make_pair(l[left], r[left]));
				left--;
				continue;
			}
			if(((*idx).first) <= r[left])
			{
				// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << "\n";
				break;
			}
			s.insert(make_pair(l[left], r[left]));
			left--;
		}
		//actually from left + 1, but since left + 1 will be taken, we assign it as left
		max_left[right] = left;
		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";

	left = n;
	s.clear();
	for(int right = n; right > 0; right--)
	{
		while(left > 0)
		{
			auto idx = s.lower_bound(make_pair(l[left], r[left]));
			// cout << "(*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
			if(s.size() == 0)
			{
				// cout << "left = " << left << ", right = " << right << ", at s.size() == 0\n";
				// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
				s.insert(make_pair(l[left], r[left]));
				left--;
				continue;
			}
			idx = prev(idx);
			if(idx == prev(s.begin()))
			{
				// cout << "left = " << left << ", right = " << right << ", at s.begin() after reducing one number\n";
				// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
				s.insert(make_pair(l[left], r[left]));
				left--;
				continue;
			}
			if(((*idx).second) >= l[left])
			{
				// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
				break;
			}
			// cout << "left = " << left << ", right = " << right << ", nothing happened\n";
			// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
			s.insert(make_pair(l[left], r[left]));
			left--;
		}
		max_left[right] = max(max_left[right], left);
		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 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 38380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 40296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 38380 KB Output isn't correct
2 Halted 0 ms 0 KB -