oj.uz

Submission #213198

# Submission time Handle Problem Language Result Execution time Memory
213198 2020-03-25T08:48:10 Z someone_aa Examination (JOI19_examination) C++17
100 / 100
 2177 ms 165880 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
using namespace __gnu_pbds;
const int maxn = 100100;

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> order_set;

struct query{
public:
	int amin, bmin;
	int smin;
}professor[maxn];

struct score {
public:
	int testa, testb;
	int testsum;
}students[maxn];

bool compare_students(score a, score b) {
	return a.testsum > b.testsum;
}

vector<int>qs[maxn];
int result[maxn];
int n, q, sz;

order_set segment_tree[4*maxn];
set<int>st;
map<int,int>cind;
int originalval[maxn];

void update(int aval, int bval, int li=0, int ri=sz-1, int index=1) {
	segment_tree[index].insert(mp(bval, segment_tree[index].size()));
	if(li != ri) {
		int mid = (li + ri) / 2;

		if(aval <= originalval[mid]) update(aval, bval, li, mid, 2*index);
		else update(aval, bval, mid+1, ri, 2*index+1);
	}
}

int query(int qa, int qb, int li=0, int ri=sz-1, int index=1) {
	if(originalval[ri] < qa) return 0;
	else if(originalval[li] >= qa) {
		int tmp = segment_tree[index].order_of_key(mp(qb, -1));
		return (segment_tree[index].size() - tmp);
	}
	else {
		int mid = (li + ri) / 2;
		return query(qa, qb, li, mid, 2*index) + query(qa, qb, mid+1, ri, 2*index+1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>students[i].testa>>students[i].testb;
		st.insert(students[i].testa);
		students[i].testsum = students[i].testa + students[i].testb;
	}
	sort(students+1, students+n+1, compare_students);

	int br = 0;
	for(int i:st) {
		originalval[br] = i;
		br++;
	}
	sz = br;

	for(int i=1;i<=q;i++) {
		cin>>professor[i].amin>>professor[i].bmin>>professor[i].smin;

		if(professor[i].smin > students[1].testsum) {
			result[i] = 0;
			continue;
		}

		int index = 1;
		for(int cekor=n/2;cekor>0;cekor/=2) {
			while(index+cekor<=n && students[index+cekor].testsum >= professor[i].smin) index += cekor;
		}
		qs[index].push_back(i);
	}

	for(int i=1;i<=n;i++) {
		update(students[i].testa, students[i].testb);

		for(auto j:qs[i]) {
			result[j] = query(professor[j].amin, professor[j].bmin);
		}
	}

	for(int i=1;i<=q;i++) {
		cout<<result[i]<<"\n";
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 40320 KB Output is correct
2 Correct 36 ms 40312 KB Output is correct
3 Correct 36 ms 40320 KB Output is correct
4 Correct 37 ms 40320 KB Output is correct
5 Correct 36 ms 40320 KB Output is correct
6 Correct 35 ms 40320 KB Output is correct
7 Correct 52 ms 43128 KB Output is correct
8 Correct 52 ms 43136 KB Output is correct
9 Correct 54 ms 43128 KB Output is correct
10 Correct 52 ms 43128 KB Output is correct
11 Correct 44 ms 41464 KB Output is correct
12 Correct 44 ms 41344 KB Output is correct
13 Correct 55 ms 43128 KB Output is correct
14 Correct 52 ms 43128 KB Output is correct
15 Correct 52 ms 43128 KB Output is correct
16 Correct 38 ms 40696 KB Output is correct
17 Correct 50 ms 43128 KB Output is correct
18 Correct 38 ms 40696 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2059 ms 156020 KB Output is correct
2 Correct 1846 ms 156008 KB Output is correct
3 Correct 1839 ms 156020 KB Output is correct
4 Correct 1279 ms 155124 KB Output is correct
5 Correct 430 ms 74224 KB Output is correct
6 Correct 371 ms 73584 KB Output is correct
7 Correct 1913 ms 155892 KB Output is correct
8 Correct 1624 ms 155892 KB Output is correct
9 Correct 1527 ms 155892 KB Output is correct
10 Correct 144 ms 51824 KB Output is correct
11 Correct 991 ms 155124 KB Output is correct
12 Correct 173 ms 50928 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2059 ms 156020 KB Output is correct
2 Correct 1846 ms 156008 KB Output is correct
3 Correct 1839 ms 156020 KB Output is correct
4 Correct 1279 ms 155124 KB Output is correct
5 Correct 430 ms 74224 KB Output is correct
6 Correct 371 ms 73584 KB Output is correct
7 Correct 1913 ms 155892 KB Output is correct
8 Correct 1624 ms 155892 KB Output is correct
9 Correct 1527 ms 155892 KB Output is correct
10 Correct 144 ms 51824 KB Output is correct
11 Correct 991 ms 155124 KB Output is correct
12 Correct 173 ms 50928 KB Output is correct
13 Correct 1709 ms 157432 KB Output is correct
14 Correct 1957 ms 157048 KB Output is correct
15 Correct 1849 ms 156024 KB Output is correct
16 Correct 1306 ms 156792 KB Output is correct
17 Correct 452 ms 75768 KB Output is correct
18 Correct 405 ms 73720 KB Output is correct
19 Correct 1929 ms 157432 KB Output is correct
20 Correct 1929 ms 157432 KB Output is correct
21 Correct 1613 ms 157432 KB Output is correct
22 Correct 150 ms 51948 KB Output is correct
23 Correct 1016 ms 154996 KB Output is correct
24 Correct 177 ms 50932 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 40320 KB Output is correct
2 Correct 36 ms 40312 KB Output is correct
3 Correct 36 ms 40320 KB Output is correct
4 Correct 37 ms 40320 KB Output is correct
5 Correct 36 ms 40320 KB Output is correct
6 Correct 35 ms 40320 KB Output is correct
7 Correct 52 ms 43128 KB Output is correct
8 Correct 52 ms 43136 KB Output is correct
9 Correct 54 ms 43128 KB Output is correct
10 Correct 52 ms 43128 KB Output is correct
11 Correct 44 ms 41464 KB Output is correct
12 Correct 44 ms 41344 KB Output is correct
13 Correct 55 ms 43128 KB Output is correct
14 Correct 52 ms 43128 KB Output is correct
15 Correct 52 ms 43128 KB Output is correct
16 Correct 38 ms 40696 KB Output is correct
17 Correct 50 ms 43128 KB Output is correct
18 Correct 38 ms 40696 KB Output is correct
19 Correct 2059 ms 156020 KB Output is correct
20 Correct 1846 ms 156008 KB Output is correct
21 Correct 1839 ms 156020 KB Output is correct
22 Correct 1279 ms 155124 KB Output is correct
23 Correct 430 ms 74224 KB Output is correct
24 Correct 371 ms 73584 KB Output is correct
25 Correct 1913 ms 155892 KB Output is correct
26 Correct 1624 ms 155892 KB Output is correct
27 Correct 1527 ms 155892 KB Output is correct
28 Correct 144 ms 51824 KB Output is correct
29 Correct 991 ms 155124 KB Output is correct
30 Correct 173 ms 50928 KB Output is correct
31 Correct 1709 ms 157432 KB Output is correct
32 Correct 1957 ms 157048 KB Output is correct
33 Correct 1849 ms 156024 KB Output is correct
34 Correct 1306 ms 156792 KB Output is correct
35 Correct 452 ms 75768 KB Output is correct
36 Correct 405 ms 73720 KB Output is correct
37 Correct 1929 ms 157432 KB Output is correct
38 Correct 1929 ms 157432 KB Output is correct
39 Correct 1613 ms 157432 KB Output is correct
40 Correct 150 ms 51948 KB Output is correct
41 Correct 1016 ms 154996 KB Output is correct
42 Correct 177 ms 50932 KB Output is correct
43 Correct 1942 ms 165880 KB Output is correct
44 Correct 1784 ms 165880 KB Output is correct
45 Correct 2177 ms 165496 KB Output is correct
46 Correct 1190 ms 164472 KB Output is correct
47 Correct 452 ms 77048 KB Output is correct
48 Correct 372 ms 73080 KB Output is correct
49 Correct 2011 ms 165368 KB Output is correct
50 Correct 1865 ms 165868 KB Output is correct
51 Correct 1618 ms 165368 KB Output is correct
52 Correct 269 ms 54648 KB Output is correct
53 Correct 1032 ms 162248 KB Output is correct