Submission #1276814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276814		SoSmolSten	Examination (JOI19_examination)	C++20	20 / 100	180 ms	14992 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; bool q;
	void input(int idx, bool query){
		cin >> a >> b;
		if(!query) cin >> c;
		else c = a + b;
		i = idx;
		q = query;
	}
	void output(){
		cout << a << ' ' << b << ' ' << c << ' ' << i << ' ' << q << '\n';

	}
	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);
	for(int i = 1; i <= n + m; ++i) a[i].c = lower_bound(arr.begin(), arr.end(), a[i].c) - arr.begin() + 1;
 	// for(int i = 1; i <= n + m; ++i) a[i].output();
		// cout << '\n';
	solve(1, n + m);
	// for(int i = 1; i <= n + m; ++i) a[i].output();

	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: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57