oj.uz

Submission #862681

# Submission time Handle Problem Language Result Execution time Memory
862681 2023-10-18T20:10:56 Z Cyber_Wolf Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 113 ms 11288 KB 
#include <bits/stdc++.h>

using namespace std;

#define lg long long 

const lg N = 2e5+5;

lg l[N], r[N], anc[N][20], n;

int main()
{
	lg n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	lg en = 1;
	multiset<array<lg, 2>> se;
	se.insert({l[1], r[1]});
	for(int i = 1; i <= n; i++)
	{
		while(en+1 <= n)
		{
			auto it = se.lower_bound({l[en], l[en]});
			if(it != se.end() && (*it)[0] >= l[en] && (*it)[0] <= r[en])
			{
				break;
			}
			if(it != se.begin())
			{
				it--;
				if((*it)[1] >= l[en] && (*it)[1] <= r[en])
				{
					break;
				}
			}
			se.insert({l[en], r[en]});
			en++;
		}
		anc[i][0] = en;
		se.erase(se.find({l[i], r[i]}));
	}
	for(int i = n; i >= 1; i--)
	{
		for(int j = 1; j < 20; j++)
		{
			anc[i][j] = anc[anc[i][j-1]+1][j-1];
		}
	}
	lg q;
	cin >> q;
	while(q--)
	{
		lg a, b;
		cin >> a >> b;
		lg ans = 0;
		for(int i = 19; i >= 0 && a <= b; i--)
		{
			if(anc[a][i] <= b && anc[a][i])
			{
				ans += (1ll << i);
				a = anc[a][i]+1;
			}
		}
		cout << ans << '\n';
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 11092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4696 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4696 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 11288 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 11092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -