Submission #1273391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273391		nhq0914	Examination (JOI19_examination)	C++17	0 / 100	169 ms	8040 KiB

examination

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define vi vector <int>
#define pb push_back
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

template <typename T>
	using pq_min = priority_queue <T, vector <T>, greater <T>>;

//template <typename T, class F = less <T>>
//	void compress(vector <T> &vec, const F &cmp = {}){
//		bool sorted = true;
//		for(int i = 1; i < (int)vec.size(); ++i)
//			if(!cmp(vec[i], vec[i - 1])){
//				sorted = false;
//				break;
//			}
//		if(!sorted) sort(all(vec), cmp);
//		vec.erase(unique(all(vec)), vec.end());
//	}

const int maxn = 1e5 + 123;

struct info{
	int a, b, c, i;

	info (int _a = 0, int _b = 0, int _c = 0, int _i = -1){
		a = _a;
		b = _b;
		c = _c;
		i = _i;
	}

	bool operator < (const info &x) const{
		if(c == x.c) return i == -1;
		return c > x.c;
	}
};

struct sub_info{ //khử z
	int a, b, i;
};

struct BIT{
	int n;
	vi fwt;

	BIT(const int &n){
		this -> n = n + 1;
		fwt.resize(n + 5);
	}

	void update(int i, int v){
		for(; i <= n; i += i & -i)
			fwt[i] += v;
	}

	int get(int i){
		int res = 0;
		for(; i; i -= i & -i)
			res += fwt[i];
		return res;
	}
};

int n, q;
int ans[maxn];

vector <info> infor;
vi cpr;

inline int getID(const int &x){
	return upper_bound(all(cpr), x, greater <int> ()) - cpr.begin() + 2;
}

void dnc(int l, int r){
	if(l == r) return;

	int mid = (l + r) / 2;

	cpr.clear();
	vector <pair <int, int>> student;
	for(int i = l; i <= mid; ++i)
		if(infor[i].i == -1){
			student.pb({infor[i].a, infor[i].b});
			cpr.pb(infor[i].a);
		}
	vector <sub_info> professor;
	for(int i = mid + 1; i <= r; ++i)
		if(infor[i].i != -1)
			professor.pb({infor[i].a, infor[i].b, infor[i].i});

	sort(all(student), [&] (const pair <int, int> &a, const pair <int, int> &b){
		return a.second > b.second;
	});
	sort(all(professor), [&] (const sub_info &a, const sub_info &b){
		return a.b > b.b;
	});

	sort(rall(cpr));
	cpr.erase(unique(all(cpr)), cpr.end());
	BIT bit((int) cpr.size());

	int pt = 0;
	for(auto &x : professor){
		while(pt < (int)student.size() && student[pt].second >= x.b){
			bit.update(getID(student[pt].first), 1);
			++pt;
		}
		ans[x.i] += bit.get(getID(x.a));
	}

	dnc(l, mid);
	dnc(mid + 1, r);
}

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

	cin >> n >> q;

	infor.resize(n + q);

	for(int i = 0; i < n; ++i){
		auto &x = infor[i];
		cin >> x.a >> x.b;
		x.c = x.a + x.b;
	}

	for(int i = 0; i < q; ++i){
		auto &x = infor[n + i];
		cin >> x.a >> x.b >> x.c;
		x.i = i;
	}

	sort(all(infor));

	dnc(0, (int) infor.size() - 1);

	for(int i = 0; i < q; ++i) cout << ans[i] << '\n';

	return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57