oj.uz

Submission #798711

# Submission time Handle Problem Language Result Execution time Memory
798711 2023-07-31T01:26:13 Z tlnk07 Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 1000 ms 8456 KB 
#include<bits/stdc++.h>
using namespace std;

long long n, q, x, y;
pair<int, int> a[200001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; ++i)	cin >> a[i].first >> a[i].second;
	cin >> q;
	while(q--)
	{
		cin >> x >> y;
		vector<pair<int, int>> vec(a + x, a + y + 1);
		vec.push_back({INT_MAX, INT_MAX});
		sort(vec.begin(), vec.end());
		long long cnt = 0;
		pair<int, int> t;
		while(vec.size() > 1)
		{
			t = vec[0];
			vec.erase(vec.begin() + 0);
			while(t.first != INT_MAX)
			{
				int l = 0, r = vec.size() - 1;
				while(l < r)
				{
					long long mid = (l + r) / 2;
					if(vec[mid].first <= t.second)	l = mid + 1;
					else	r = mid;
				}
				if(vec[l].first == INT_MAX || vec[l].first <= t.second)	break;
				t = vec[l];
				vec.erase(vec.begin() + l);
			}
			++cnt;
		}
		cout << cnt << "\n";
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 8456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 7192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 8456 KB Time limit exceeded
2 Halted 0 ms 0 KB -