oj.uz

Submission #213196

# Submission time Handle Problem Language Result Execution time Memory
213196 2020-03-25T08:46:19 Z someone_aa Examination (JOI19_examination) C++17
100 / 100
 2526 ms 166056 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) {
		// binary search on order set
		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() {
	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++) {
		//cout<<students[i].testa<<" "<<students[i].testb<<" - "<<students[i].testsum<<"\n";
		update(students[i].testa, students[i].testb);

		for(auto j:qs[i]) {
			//cout<<"Here query: "<<j<<"\n";
			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 39 ms 40320 KB Output is correct
2 Correct 42 ms 40448 KB Output is correct
3 Correct 39 ms 40320 KB Output is correct
4 Correct 38 ms 40312 KB Output is correct
5 Correct 37 ms 40312 KB Output is correct
6 Correct 38 ms 40320 KB Output is correct
7 Correct 64 ms 43000 KB Output is correct
8 Correct 67 ms 43128 KB Output is correct
9 Correct 63 ms 43000 KB Output is correct
10 Correct 58 ms 43000 KB Output is correct
11 Correct 51 ms 41336 KB Output is correct
12 Correct 49 ms 41336 KB Output is correct
13 Correct 60 ms 43128 KB Output is correct
14 Correct 64 ms 43128 KB Output is correct
15 Correct 59 ms 43000 KB Output is correct
16 Correct 45 ms 40696 KB Output is correct
17 Correct 58 ms 43128 KB Output is correct
18 Correct 43 ms 40568 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2221 ms 153756 KB Output is correct
2 Correct 2262 ms 156096 KB Output is correct
3 Correct 2416 ms 156016 KB Output is correct
4 Correct 1517 ms 155364 KB Output is correct
5 Correct 556 ms 74276 KB Output is correct
6 Correct 486 ms 73588 KB Output is correct
7 Correct 2082 ms 156016 KB Output is correct
8 Correct 2108 ms 155888 KB Output is correct
9 Correct 1912 ms 155912 KB Output is correct
10 Correct 262 ms 52016 KB Output is correct
11 Correct 1182 ms 154992 KB Output is correct
12 Correct 240 ms 50932 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2221 ms 153756 KB Output is correct
2 Correct 2262 ms 156096 KB Output is correct
3 Correct 2416 ms 156016 KB Output is correct
4 Correct 1517 ms 155364 KB Output is correct
5 Correct 556 ms 74276 KB Output is correct
6 Correct 486 ms 73588 KB Output is correct
7 Correct 2082 ms 156016 KB Output is correct
8 Correct 2108 ms 155888 KB Output is correct
9 Correct 1912 ms 155912 KB Output is correct
10 Correct 262 ms 52016 KB Output is correct
11 Correct 1182 ms 154992 KB Output is correct
12 Correct 240 ms 50932 KB Output is correct
13 Correct 2273 ms 157468 KB Output is correct
14 Correct 2273 ms 157176 KB Output is correct
15 Correct 2202 ms 156276 KB Output is correct
16 Correct 1408 ms 156792 KB Output is correct
17 Correct 598 ms 75700 KB Output is correct
18 Correct 512 ms 73720 KB Output is correct
19 Correct 2131 ms 157688 KB Output is correct
20 Correct 2368 ms 157416 KB Output is correct
21 Correct 1934 ms 157560 KB Output is correct
22 Correct 273 ms 51880 KB Output is correct
23 Correct 1161 ms 154996 KB Output is correct
24 Correct 237 ms 50932 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40320 KB Output is correct
2 Correct 42 ms 40448 KB Output is correct
3 Correct 39 ms 40320 KB Output is correct
4 Correct 38 ms 40312 KB Output is correct
5 Correct 37 ms 40312 KB Output is correct
6 Correct 38 ms 40320 KB Output is correct
7 Correct 64 ms 43000 KB Output is correct
8 Correct 67 ms 43128 KB Output is correct
9 Correct 63 ms 43000 KB Output is correct
10 Correct 58 ms 43000 KB Output is correct
11 Correct 51 ms 41336 KB Output is correct
12 Correct 49 ms 41336 KB Output is correct
13 Correct 60 ms 43128 KB Output is correct
14 Correct 64 ms 43128 KB Output is correct
15 Correct 59 ms 43000 KB Output is correct
16 Correct 45 ms 40696 KB Output is correct
17 Correct 58 ms 43128 KB Output is correct
18 Correct 43 ms 40568 KB Output is correct
19 Correct 2221 ms 153756 KB Output is correct
20 Correct 2262 ms 156096 KB Output is correct
21 Correct 2416 ms 156016 KB Output is correct
22 Correct 1517 ms 155364 KB Output is correct
23 Correct 556 ms 74276 KB Output is correct
24 Correct 486 ms 73588 KB Output is correct
25 Correct 2082 ms 156016 KB Output is correct
26 Correct 2108 ms 155888 KB Output is correct
27 Correct 1912 ms 155912 KB Output is correct
28 Correct 262 ms 52016 KB Output is correct
29 Correct 1182 ms 154992 KB Output is correct
30 Correct 240 ms 50932 KB Output is correct
31 Correct 2273 ms 157468 KB Output is correct
32 Correct 2273 ms 157176 KB Output is correct
33 Correct 2202 ms 156276 KB Output is correct
34 Correct 1408 ms 156792 KB Output is correct
35 Correct 598 ms 75700 KB Output is correct
36 Correct 512 ms 73720 KB Output is correct
37 Correct 2131 ms 157688 KB Output is correct
38 Correct 2368 ms 157416 KB Output is correct
39 Correct 1934 ms 157560 KB Output is correct
40 Correct 273 ms 51880 KB Output is correct
41 Correct 1161 ms 154996 KB Output is correct
42 Correct 237 ms 50932 KB Output is correct
43 Correct 2379 ms 166056 KB Output is correct
44 Correct 2300 ms 165976 KB Output is correct
45 Correct 2526 ms 165600 KB Output is correct
46 Correct 1471 ms 164472 KB Output is correct
47 Correct 653 ms 76920 KB Output is correct
48 Correct 478 ms 73080 KB Output is correct
49 Correct 2489 ms 165752 KB Output is correct
50 Correct 2257 ms 165752 KB Output is correct
51 Correct 2097 ms 165576 KB Output is correct
52 Correct 419 ms 54620 KB Output is correct
53 Correct 1255 ms 162288 KB Output is correct