oj.uz

Submission #880478

# Submission time Handle Problem Language Result Execution time Memory
880478 2023-11-29T13:34:25 Z Youssif_Elkadi Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 1000 ms 31020 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] += lazy[node];
	if (l != r)
		lazy[node * 2] += lazy[node], lazy[node * 2 + 1] += lazy[node];
	lazy[node] = 0;
}
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;
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		int lst = l;
		int ans = 1;
		for (int i = l; i <= r; i++)
		{
			update(arr[i].first, arr[i].second, 1);
			if (query(arr[i].first, arr[i].second) > 1)
			{
				ans++;
				for (int k = lst; k < i; k++)
					update(arr[k].first, arr[k].second, -1);
				lst = i;
			}
		}
		for (int i = lst; i <= r; i++)
			update(arr[i].first, arr[i].second, -1);
		cout << ans << "\n";
	}
}
/*
3
1
3
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 30128 KB Output is correct
2 Correct 610 ms 30036 KB Output is correct
3 Correct 615 ms 29900 KB Output is correct
4 Correct 606 ms 30128 KB Output is correct
5 Correct 691 ms 30980 KB Output is correct
6 Correct 31 ms 3932 KB Output is correct
7 Correct 41 ms 3932 KB Output is correct
8 Correct 47 ms 3928 KB Output is correct
9 Correct 60 ms 3932 KB Output is correct
10 Correct 62 ms 3920 KB Output is correct
11 Correct 517 ms 30520 KB Output is correct
12 Correct 401 ms 29520 KB Output is correct
13 Correct 366 ms 29328 KB Output is correct
14 Correct 459 ms 30540 KB Output is correct
15 Correct 425 ms 30032 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 32 ms 3924 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 5172 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 1079 ms 5172 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 1085 ms 31020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 30128 KB Output is correct
2 Correct 610 ms 30036 KB Output is correct
3 Correct 615 ms 29900 KB Output is correct
4 Correct 606 ms 30128 KB Output is correct
5 Correct 691 ms 30980 KB Output is correct
6 Correct 31 ms 3932 KB Output is correct
7 Correct 41 ms 3932 KB Output is correct
8 Correct 47 ms 3928 KB Output is correct
9 Correct 60 ms 3932 KB Output is correct
10 Correct 62 ms 3920 KB Output is correct
11 Correct 517 ms 30520 KB Output is correct
12 Correct 401 ms 29520 KB Output is correct
13 Correct 366 ms 29328 KB Output is correct
14 Correct 459 ms 30540 KB Output is correct
15 Correct 425 ms 30032 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 32 ms 3924 KB Output is correct
18 Execution timed out 1079 ms 5172 KB Time limit exceeded
19 Halted 0 ms 0 KB -