제출 #1273398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273398		nhq0914	Examination (JOI19_examination)	C++17	2 / 100	3028 ms	8860 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>>;

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;
	}
} bit(2 * maxn);

int n, q;
int ans[maxn];

vector <info> infor;
vi cpr;

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

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

	int mid = (l + r) / 2;

	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});
	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;
	});

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

	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;
		cpr.pb(x.a);
	}

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

	sort(all(infor));
	sort(rall(cpr));
	cpr.erase(unique(all(cpr)), cpr.end());

	for(auto &x : infor) x.a = getID(x.a);

	dnc(0, n + q - 1);

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

	return 0;
}

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