oj.uz

Submission #131645

# Submission time Handle Problem Language Result Execution time Memory
131645 2019-07-17T11:05:46 Z MrTEK Examination (JOI19_examination) C++14
100 / 100
 2168 ms 97216 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

using namespace __gnu_pbds;
using ordered_set = tree<ii, null_type,less<ii>, rb_tree_tag,tree_order_statistics_node_update>;

const int N = 2e5 + 5;
const int inf = 1e9;

vector <int> v;
vector <pair<ii,ii>> queries;
map <int,int> id;
int answer,n,q,s[N],t[N],x[N],y[N],z[N],ans[N],tim;
ordered_set seg[N];

int query(int x,int val) {
	int answer = 0;
	for ( ; x <= N ; x += (x & -x))
		answer += seg[x].order_of_key({-val,inf});
	return answer;
}

void update(int x,int val) {
	for ( ; x > 0 ; x -= (x & -x))
		seg[x].insert({-val,++tim});
}

int main() {
	// freopen("04-01.txt","r",stdin);
	// freopen("04-01o2.txt","w",stdout);
	cin >> n >> q;
	for (int i = 1 ; i <= n ; i++) {
		cin >> s[i] >> t[i];
		v.push_back(t[i]);
		queries.push_back({{s[i],inf},{t[i],s[i] + t[i]}});
	}
	for (int i = 1 ; i <= q ; i++) {
		cin >> x[i] >> y[i] >> z[i];
		v.push_back(y[i]);
		queries.push_back({{x[i],i},{y[i],z[i]}});
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end()) - v.begin());
	int dsa = 0;
	for (auto i : v)
		id[i] = ++dsa;
	sort(queries.begin(),queries.end());
	reverse(queries.begin(),queries.end());
	for (auto i : queries) {
		if (i.first.second == inf)
			update(id[i.second.first],i.second.second);
		else
			ans[i.first.second] = query(id[i.second.first],i.second.second);
	}
	for (int i = 1 ; i <= q ; i++)
		cout << ans[i] << "\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19196 KB Output is correct
2 Correct 26 ms 19064 KB Output is correct
3 Correct 26 ms 19064 KB Output is correct
4 Correct 26 ms 19064 KB Output is correct
5 Correct 28 ms 19108 KB Output is correct
6 Correct 26 ms 19192 KB Output is correct
7 Correct 52 ms 20856 KB Output is correct
8 Correct 51 ms 20856 KB Output is correct
9 Correct 51 ms 20960 KB Output is correct
10 Correct 40 ms 19832 KB Output is correct
11 Correct 46 ms 20856 KB Output is correct
12 Correct 36 ms 19704 KB Output is correct
13 Correct 50 ms 20856 KB Output is correct
14 Correct 51 ms 20888 KB Output is correct
15 Correct 50 ms 20856 KB Output is correct
16 Correct 44 ms 20900 KB Output is correct
17 Correct 40 ms 19664 KB Output is correct
18 Correct 35 ms 19576 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 82844 KB Output is correct
2 Correct 1581 ms 82832 KB Output is correct
3 Correct 1611 ms 82784 KB Output is correct
4 Correct 398 ms 39220 KB Output is correct
5 Correct 978 ms 81872 KB Output is correct
6 Correct 335 ms 38356 KB Output is correct
7 Correct 1738 ms 82704 KB Output is correct
8 Correct 1634 ms 82176 KB Output is correct
9 Correct 1521 ms 82128 KB Output is correct
10 Correct 923 ms 81756 KB Output is correct
11 Correct 359 ms 33792 KB Output is correct
12 Correct 290 ms 32856 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 82844 KB Output is correct
2 Correct 1581 ms 82832 KB Output is correct
3 Correct 1611 ms 82784 KB Output is correct
4 Correct 398 ms 39220 KB Output is correct
5 Correct 978 ms 81872 KB Output is correct
6 Correct 335 ms 38356 KB Output is correct
7 Correct 1738 ms 82704 KB Output is correct
8 Correct 1634 ms 82176 KB Output is correct
9 Correct 1521 ms 82128 KB Output is correct
10 Correct 923 ms 81756 KB Output is correct
11 Correct 359 ms 33792 KB Output is correct
12 Correct 290 ms 32856 KB Output is correct
13 Correct 1840 ms 83028 KB Output is correct
14 Correct 1716 ms 82912 KB Output is correct
15 Correct 1558 ms 82628 KB Output is correct
16 Correct 469 ms 39560 KB Output is correct
17 Correct 969 ms 82500 KB Output is correct
18 Correct 344 ms 38368 KB Output is correct
19 Correct 1706 ms 83112 KB Output is correct
20 Correct 1729 ms 83088 KB Output is correct
21 Correct 1751 ms 82992 KB Output is correct
22 Correct 876 ms 81688 KB Output is correct
23 Correct 362 ms 33888 KB Output is correct
24 Correct 291 ms 32872 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19196 KB Output is correct
2 Correct 26 ms 19064 KB Output is correct
3 Correct 26 ms 19064 KB Output is correct
4 Correct 26 ms 19064 KB Output is correct
5 Correct 28 ms 19108 KB Output is correct
6 Correct 26 ms 19192 KB Output is correct
7 Correct 52 ms 20856 KB Output is correct
8 Correct 51 ms 20856 KB Output is correct
9 Correct 51 ms 20960 KB Output is correct
10 Correct 40 ms 19832 KB Output is correct
11 Correct 46 ms 20856 KB Output is correct
12 Correct 36 ms 19704 KB Output is correct
13 Correct 50 ms 20856 KB Output is correct
14 Correct 51 ms 20888 KB Output is correct
15 Correct 50 ms 20856 KB Output is correct
16 Correct 44 ms 20900 KB Output is correct
17 Correct 40 ms 19664 KB Output is correct
18 Correct 35 ms 19576 KB Output is correct
19 Correct 1678 ms 82844 KB Output is correct
20 Correct 1581 ms 82832 KB Output is correct
21 Correct 1611 ms 82784 KB Output is correct
22 Correct 398 ms 39220 KB Output is correct
23 Correct 978 ms 81872 KB Output is correct
24 Correct 335 ms 38356 KB Output is correct
25 Correct 1738 ms 82704 KB Output is correct
26 Correct 1634 ms 82176 KB Output is correct
27 Correct 1521 ms 82128 KB Output is correct
28 Correct 923 ms 81756 KB Output is correct
29 Correct 359 ms 33792 KB Output is correct
30 Correct 290 ms 32856 KB Output is correct
31 Correct 1840 ms 83028 KB Output is correct
32 Correct 1716 ms 82912 KB Output is correct
33 Correct 1558 ms 82628 KB Output is correct
34 Correct 469 ms 39560 KB Output is correct
35 Correct 969 ms 82500 KB Output is correct
36 Correct 344 ms 38368 KB Output is correct
37 Correct 1706 ms 83112 KB Output is correct
38 Correct 1729 ms 83088 KB Output is correct
39 Correct 1751 ms 82992 KB Output is correct
40 Correct 876 ms 81688 KB Output is correct
41 Correct 362 ms 33888 KB Output is correct
42 Correct 291 ms 32872 KB Output is correct
43 Correct 2111 ms 89684 KB Output is correct
44 Correct 2145 ms 94632 KB Output is correct
45 Correct 1888 ms 94424 KB Output is correct
46 Correct 538 ms 40680 KB Output is correct
47 Correct 1154 ms 92964 KB Output is correct
48 Correct 322 ms 38368 KB Output is correct
49 Correct 2106 ms 94600 KB Output is correct
50 Correct 1981 ms 97216 KB Output is correct
51 Correct 2168 ms 96996 KB Output is correct
52 Correct 992 ms 92768 KB Output is correct
53 Correct 403 ms 34680 KB Output is correct