oj.uz

Submission #131863

# Submission time Handle Problem Language Result Execution time Memory
131863 2019-07-17T20:24:27 Z tutis Examination (JOI19_examination) C++17
100 / 100
 2250 ms 133832 KB 
/*input
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
struct query
{
	int i;
	int a[3];
};
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>A[202020];
int tim = 0;
void add(int x, int y)
{
	while (x < 202020)
	{
		A[x].insert({y, tim++});
		x += x & (-x);
	}
}
int get(int x, int y)
{
	x = min(x, 202019);
	int ans = 0;
	while (x > 0)
	{
		ans += A[x].size() - (A[x].order_of_key({y, -1}));
		x -= (x & (-x));
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int>a[n];
	map<int, int>M;
	for (int i = 0; i < n; i++)
	{
		int s, t;
		cin >> s >> t;
		M[t + 2] = -1;
		a[i] = {s, t, s + t};
	}
	sort(a, a + n, [&](vector<int>x, vector<int>y) {return x[0] > y[0];});
	query Q[q];
	for (int i = 0; i < q; i++)
	{
		Q[i].i = i;
		cin >> Q[i].a[0] >> Q[i].a[1] >> Q[i].a[2];
		M[Q[i].a[1] + 1] = -1;
	}
	sort(Q, Q + q, [&](query a, query b) {return a.a[0] > b.a[0];});
	int timer = 1;
	for (auto &i : M)
	{
		i.second = timer++;
	}
	int i = 0;
	int ans[q];
	for (query x : Q)
	{
		while (i < n && a[i][0] >= x.a[0])
		{
			add(M[a[i][1] + 2], a[i][2]);
			i++;
		}
		ans[x.i] = get(1e6, x.a[2]) - get(M[x.a[1] + 1], x.a[2]);
	}
	for (int i = 0; i < q; i++)
		cout << ans[i] << "\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19320 KB Output is correct
2 Correct 29 ms 19320 KB Output is correct
3 Correct 26 ms 19320 KB Output is correct
4 Correct 26 ms 19320 KB Output is correct
5 Correct 26 ms 19320 KB Output is correct
6 Correct 26 ms 19320 KB Output is correct
7 Correct 50 ms 21980 KB Output is correct
8 Correct 49 ms 22008 KB Output is correct
9 Correct 50 ms 22056 KB Output is correct
10 Correct 55 ms 22580 KB Output is correct
11 Correct 48 ms 22008 KB Output is correct
12 Correct 50 ms 22520 KB Output is correct
13 Correct 50 ms 22236 KB Output is correct
14 Correct 48 ms 22136 KB Output is correct
15 Correct 50 ms 22088 KB Output is correct
16 Correct 46 ms 22136 KB Output is correct
17 Correct 53 ms 22776 KB Output is correct
18 Correct 52 ms 22792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1713 ms 94012 KB Output is correct
2 Correct 1677 ms 94152 KB Output is correct
3 Correct 1628 ms 94268 KB Output is correct
4 Correct 1458 ms 128632 KB Output is correct
5 Correct 1347 ms 94132 KB Output is correct
6 Correct 1390 ms 128752 KB Output is correct
7 Correct 2047 ms 94276 KB Output is correct
8 Correct 1580 ms 93000 KB Output is correct
9 Correct 1494 ms 92892 KB Output is correct
10 Correct 1356 ms 93916 KB Output is correct
11 Correct 1204 ms 133632 KB Output is correct
12 Correct 2051 ms 133596 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1713 ms 94012 KB Output is correct
2 Correct 1677 ms 94152 KB Output is correct
3 Correct 1628 ms 94268 KB Output is correct
4 Correct 1458 ms 128632 KB Output is correct
5 Correct 1347 ms 94132 KB Output is correct
6 Correct 1390 ms 128752 KB Output is correct
7 Correct 2047 ms 94276 KB Output is correct
8 Correct 1580 ms 93000 KB Output is correct
9 Correct 1494 ms 92892 KB Output is correct
10 Correct 1356 ms 93916 KB Output is correct
11 Correct 1204 ms 133632 KB Output is correct
12 Correct 2051 ms 133596 KB Output is correct
13 Correct 1883 ms 94068 KB Output is correct
14 Correct 1814 ms 94168 KB Output is correct
15 Correct 1938 ms 94164 KB Output is correct
16 Correct 1539 ms 128588 KB Output is correct
17 Correct 1679 ms 94088 KB Output is correct
18 Correct 1380 ms 128808 KB Output is correct
19 Correct 2142 ms 94228 KB Output is correct
20 Correct 1920 ms 94244 KB Output is correct
21 Correct 1948 ms 93444 KB Output is correct
22 Correct 1160 ms 94028 KB Output is correct
23 Correct 1161 ms 133728 KB Output is correct
24 Correct 2250 ms 133548 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19320 KB Output is correct
2 Correct 29 ms 19320 KB Output is correct
3 Correct 26 ms 19320 KB Output is correct
4 Correct 26 ms 19320 KB Output is correct
5 Correct 26 ms 19320 KB Output is correct
6 Correct 26 ms 19320 KB Output is correct
7 Correct 50 ms 21980 KB Output is correct
8 Correct 49 ms 22008 KB Output is correct
9 Correct 50 ms 22056 KB Output is correct
10 Correct 55 ms 22580 KB Output is correct
11 Correct 48 ms 22008 KB Output is correct
12 Correct 50 ms 22520 KB Output is correct
13 Correct 50 ms 22236 KB Output is correct
14 Correct 48 ms 22136 KB Output is correct
15 Correct 50 ms 22088 KB Output is correct
16 Correct 46 ms 22136 KB Output is correct
17 Correct 53 ms 22776 KB Output is correct
18 Correct 52 ms 22792 KB Output is correct
19 Correct 1713 ms 94012 KB Output is correct
20 Correct 1677 ms 94152 KB Output is correct
21 Correct 1628 ms 94268 KB Output is correct
22 Correct 1458 ms 128632 KB Output is correct
23 Correct 1347 ms 94132 KB Output is correct
24 Correct 1390 ms 128752 KB Output is correct
25 Correct 2047 ms 94276 KB Output is correct
26 Correct 1580 ms 93000 KB Output is correct
27 Correct 1494 ms 92892 KB Output is correct
28 Correct 1356 ms 93916 KB Output is correct
29 Correct 1204 ms 133632 KB Output is correct
30 Correct 2051 ms 133596 KB Output is correct
31 Correct 1883 ms 94068 KB Output is correct
32 Correct 1814 ms 94168 KB Output is correct
33 Correct 1938 ms 94164 KB Output is correct
34 Correct 1539 ms 128588 KB Output is correct
35 Correct 1679 ms 94088 KB Output is correct
36 Correct 1380 ms 128808 KB Output is correct
37 Correct 2142 ms 94228 KB Output is correct
38 Correct 1920 ms 94244 KB Output is correct
39 Correct 1948 ms 93444 KB Output is correct
40 Correct 1160 ms 94028 KB Output is correct
41 Correct 1161 ms 133728 KB Output is correct
42 Correct 2250 ms 133548 KB Output is correct
43 Correct 2168 ms 94848 KB Output is correct
44 Correct 1949 ms 95032 KB Output is correct
45 Correct 1990 ms 95092 KB Output is correct
46 Correct 1632 ms 128788 KB Output is correct
47 Correct 1618 ms 94944 KB Output is correct
48 Correct 1456 ms 128632 KB Output is correct
49 Correct 2105 ms 95108 KB Output is correct
50 Correct 1860 ms 92152 KB Output is correct
51 Correct 1939 ms 92152 KB Output is correct
52 Correct 1493 ms 94760 KB Output is correct
53 Correct 2202 ms 133832 KB Output is correct