oj.uz

Submission #880473

# Submission time Handle Problem Language Result Execution time Memory
880473 2023-11-29T13:15:39 Z Youssif_Elkadi Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 1000 ms 34808 KB 
#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5, mod = 1e9 + 7, inf = 1e9 + 5;
int tree[N * 8 + 1], lazy[N * 8 + 1];
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(1, cor) > 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 524 ms 30292 KB Output is correct
2 Correct 518 ms 33548 KB Output is correct
3 Correct 536 ms 33620 KB Output is correct
4 Correct 556 ms 34128 KB Output is correct
5 Correct 573 ms 34808 KB Output is correct
6 Correct 36 ms 7372 KB Output is correct
7 Correct 38 ms 7532 KB Output is correct
8 Correct 43 ms 7488 KB Output is correct
9 Correct 50 ms 7448 KB Output is correct
10 Correct 61 ms 7252 KB Output is correct
11 Correct 390 ms 33940 KB Output is correct
12 Correct 351 ms 32444 KB Output is correct
13 Correct 336 ms 32512 KB Output is correct
14 Correct 344 ms 33968 KB Output is correct
15 Correct 352 ms 33360 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 33 ms 7728 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 5176 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 1018 ms 5176 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 1041 ms 31060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 30292 KB Output is correct
2 Correct 518 ms 33548 KB Output is correct
3 Correct 536 ms 33620 KB Output is correct
4 Correct 556 ms 34128 KB Output is correct
5 Correct 573 ms 34808 KB Output is correct
6 Correct 36 ms 7372 KB Output is correct
7 Correct 38 ms 7532 KB Output is correct
8 Correct 43 ms 7488 KB Output is correct
9 Correct 50 ms 7448 KB Output is correct
10 Correct 61 ms 7252 KB Output is correct
11 Correct 390 ms 33940 KB Output is correct
12 Correct 351 ms 32444 KB Output is correct
13 Correct 336 ms 32512 KB Output is correct
14 Correct 344 ms 33968 KB Output is correct
15 Correct 352 ms 33360 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 33 ms 7728 KB Output is correct
18 Execution timed out 1018 ms 5176 KB Time limit exceeded
19 Halted 0 ms 0 KB -