Submission #1273389

#TimeUsernameProblemLanguageResultExecution timeMemory
1273389nhq0914Examination (JOI19_examination)C++17
0 / 100
1 ms332 KiB
#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;
	}
};

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;

	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});
			cpr.pb(infor[i].a);
		}

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

	freopen("data.txt", "r", stdin);
	freopen("out.txt", "w", stdout);

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

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("data.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...