oj.uz

Submission #213195

# Submission time Handle Problem Language Result Execution time Memory
213195 2020-03-25T08:43:40 Z someone_aa Examination (JOI19_examination) C++17
0 / 100
 2133 ms 119396 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
using namespace std;
using namespace __gnu_pbds;
const int maxn = 100100;

typedef tree<int,null_type,less<int>,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(bval);
	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(qb);
		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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34048 KB Output is correct
2 Correct 35 ms 34048 KB Output is correct
3 Correct 35 ms 34048 KB Output is correct
4 Correct 36 ms 34048 KB Output is correct
5 Correct 37 ms 34048 KB Output is correct
6 Correct 35 ms 34048 KB Output is correct
7 Correct 58 ms 36344 KB Output is correct
8 Correct 56 ms 36216 KB Output is correct
9 Correct 57 ms 36344 KB Output is correct
10 Incorrect 52 ms 35280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2133 ms 119396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2133 ms 119396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34048 KB Output is correct
2 Correct 35 ms 34048 KB Output is correct
3 Correct 35 ms 34048 KB Output is correct
4 Correct 36 ms 34048 KB Output is correct
5 Correct 37 ms 34048 KB Output is correct
6 Correct 35 ms 34048 KB Output is correct
7 Correct 58 ms 36344 KB Output is correct
8 Correct 56 ms 36216 KB Output is correct
9 Correct 57 ms 36344 KB Output is correct
10 Incorrect 52 ms 35280 KB Output isn't correct
11 Halted 0 ms 0 KB -