제출 #1276832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276832		SoSmolSten	Examination (JOI19_examination)	C++20	100 / 100	272 ms	15732 KiB

examination

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
struct ps{ // ProfessorStudent
	int a, b, c, i, q;
	void input(int idx, int query){
		cin >> a >> b;
		if(!query) cin >> c;
		else c = a + b;
		i = idx;
		q = query;
	}
	bool operator<(const ps &x) const{
		if(a != x.a) return a > x.a; 
		if(b != x.b) return b > x.b; 
		if(c != x.c) return c > x.c; 
		if(q != x.q) return q > x.q; 
		return i > x.i;
	}
} a[N];
int cnt[N];
int ft[N];


void update(int u, int x) {
	for(; u > 0; u -= u & -u) ft[u] += x;
}

int ans(int u) {
	int sum = 0;
	for(; u < N; u += u & -u) sum += ft[u];
	return sum;
}
void solve(int l, int r);

int main (int argc, char const *argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n + m; ++i) a[i].input(i, i <= n);

	sort(a + 1, a + 1 + n + m);
	vector<int> arr;

	for(int i = 1; i <= n + m; ++i) arr.emplace_back(a[i].c);
	sort(arr.begin(), arr.end());
	for(int i = 1; i <= n + m; ++i) a[i].c = lower_bound(arr.begin(), arr.end(), a[i].c) - arr.begin() + 1;

	solve(1, n + m);

	for(int i = n + 1; i <= n + m; ++i) cout << cnt[i] << '\n';
	
	return 0;
}

void solve(int l, int r){
	if(l == r) return;
	int mid = (l + r) >> 1;
	solve(l, mid); solve(mid + 1, r);
	int i = l, j = mid + 1;
	vector<ps> tmp;
	vector<pair<int, int>> revert;
	while(i <= mid && j <= r){
		if(a[i].b >= a[j].b) {
			tmp.emplace_back(a[i]);
			update(a[i].c, a[i].q);
			revert.emplace_back(a[i].c, a[i].q);
			++i;
		} else {
			tmp.emplace_back(a[j]);
			cnt[a[j].i] += ans(a[j].c);
			++j;
		}
	}

	while(i <= mid) {
		tmp.emplace_back(a[i++]);
	}
	while(j <= r) {
		tmp.emplace_back(a[j]);
		cnt[a[j].i] += ans(a[j].c);
		++j;
	}
	for(auto [x, y] : revert) update(x, -y);
	for(int i = l; i <= r; ++i) a[i] = tmp[i-l]; 
}

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