oj.uz

Submission #880479

# Submission time Handle Problem Language Result Execution time Memory
880479 2023-11-29T13:47:06 Z Youssif_Elkadi Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 1000 ms 28808 KB 
#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5, mod = 1e9 + 7, inf = 1e9 + 5;
int tree[N * 8], lazy[N * 8];
int n;
int cor = 0;
void prob(int l, int r, int node)
{
	tree[node] = max(tree[node], lazy[node]);
	if (l != r)
		lazy[node * 2] = max(lazy[node * 2], lazy[node]), lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
}
void update(int lq, int rq, int val, int l = 1, int r = cor, int node = 1)
{
	prob(l, r, node);
	if (lq <= l && r <= rq)
	{
		lazy[node] = val;
		prob(l, r, node);
		return;
	}
	if (r < lq || l > rq)
		return;
	int mid = (l + r) / 2;
	update(lq, rq, val, l, mid, node * 2), update(lq, rq, val, mid + 1, r, node * 2 + 1);
	tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
int query(int lq, int rq, int l = 1, int r = cor, int node = 1)
{
	prob(l, r, node);
	if (lq <= l && r <= rq)
		return tree[node];
	if (r < lq || l > rq)
		return 0;
	int mid = (l + r) / 2;
	return max(query(lq, rq, l, mid, node * 2), query(lq, rq, mid + 1, r, node * 2 + 1));
}
map<int, int> mp;
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	cin >> n;
	vector<pair<int, int>> arr(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> arr[i].first >> arr[i].second, mp[arr[i].first] = 1, mp[arr[i].second] = 1;
	for (auto &v : mp)
		v.second = ++cor;
	for (int i = 1; i <= n; i++)
		arr[i].first = mp[arr[i].first], arr[i].second = mp[arr[i].second];
	int q;
	cin >> q;
	int vid = 1;
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		int ans = 1;
		for (int i = l; i <= r; i++)
		{
			if (query(arr[i].first, arr[i].second) == vid)
				ans++, vid++;
			update(arr[i].first, arr[i].second, vid);
		}
		vid++;
		cout << ans << "\n";
	}
}
/*
3
1
3
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 27984 KB Output is correct
2 Correct 567 ms 27716 KB Output is correct
3 Correct 610 ms 28024 KB Output is correct
4 Correct 629 ms 27896 KB Output is correct
5 Correct 665 ms 28808 KB Output is correct
6 Correct 34 ms 1880 KB Output is correct
7 Correct 36 ms 1884 KB Output is correct
8 Correct 43 ms 1884 KB Output is correct
9 Correct 47 ms 1884 KB Output is correct
10 Correct 52 ms 1884 KB Output is correct
11 Correct 435 ms 28748 KB Output is correct
12 Correct 365 ms 27220 KB Output is correct
13 Correct 353 ms 27476 KB Output is correct
14 Correct 382 ms 28548 KB Output is correct
15 Correct 406 ms 28008 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 40 ms 1884 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 1208 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 1074 ms 1208 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 1093 ms 28752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 27984 KB Output is correct
2 Correct 567 ms 27716 KB Output is correct
3 Correct 610 ms 28024 KB Output is correct
4 Correct 629 ms 27896 KB Output is correct
5 Correct 665 ms 28808 KB Output is correct
6 Correct 34 ms 1880 KB Output is correct
7 Correct 36 ms 1884 KB Output is correct
8 Correct 43 ms 1884 KB Output is correct
9 Correct 47 ms 1884 KB Output is correct
10 Correct 52 ms 1884 KB Output is correct
11 Correct 435 ms 28748 KB Output is correct
12 Correct 365 ms 27220 KB Output is correct
13 Correct 353 ms 27476 KB Output is correct
14 Correct 382 ms 28548 KB Output is correct
15 Correct 406 ms 28008 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 40 ms 1884 KB Output is correct
18 Execution timed out 1074 ms 1208 KB Time limit exceeded
19 Halted 0 ms 0 KB -