Submission #1273411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273411		nhq0914	Examination (JOI19_examination)	C++17	2 / 100	3044 ms	14768 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 = 2e5 + 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;
};

int n, q;
int ans[maxn];
int stk[18 * maxn], ssz = 0;
int f[maxn];

void update(int i, const int &v){
  for(; i < maxn; i += i & -i){
    f[i] += v;
    stk[ssz++] = i;
  }
}

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

void reset(){
  for(int i = 0; i < ssz; ++i)
	f[stk[i]] = 0;
  ssz = 0;
}

vector <info> infor;
vi cpr;

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

inline bool cmp1(const pair <int, int> &a, const pair <int, int> &b){
	return a.second > b.second;
}

inline bool cmp2(const sub_info &a, const sub_info &b){
	return a.b > b.b;
}

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), cmp1);
	sort(all(professor), cmp2);

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

	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