Submission #383968

#	Time	Username	Problem	Language	Result	Execution time	Memory
383968		ritul_kr_singh	Examination (JOI19_examination)	C++17	100 / 100	228 ms	14800 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' << 
#define nl << '\n'

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int _n){ a.resize((n=_n)+1); }
	void add(int i){
		for(++i; i<=n; i+=i&-i) ++a[i];
	}
	int get(int i){
		for(s=0; i>=1; i-=i&-i) s += a[i];
		return s;
	}
	int get(int l, int r){ return get(r+1) - get(l); }
};

int C(int val, vector<int> &vals){
	return lower_bound(vals.begin(), vals.end(), val) - vals.begin();
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, q; cin >> n >> q;
	array<int, 4> a[n+q];
	vector<int> vals1, vals2;
	for(int i=0; i<n; ++i){
		cin >> a[i][1] >> a[i][2];
		vals1.push_back(a[i][1]);
		vals2.push_back(a[i][2]);
		a[i][0] = a[i][1] + a[i][2];
	}
	for(int i=n; i<n+q; ++i){
		cin >> a[i][1] >> a[i][2] >> a[i][0];
		vals1.push_back(a[i][1]);
		vals2.push_back(a[i][2]);
		a[i][0] = max(a[i][0], a[i][1] + a[i][2]);
		a[i][1] -= 1e10;
		a[i][3] = i-n;
	}
	sort(a, a+n+q, greater<>());
	sort(vals1.begin(), vals1.end());
	sort(vals2.begin(), vals2.end());
	vals1.resize(unique(vals1.begin(), vals1.end()) - vals1.begin());
	vals2.resize(unique(vals2.begin(), vals2.end()) - vals2.begin());

	FenwickTree b1(n+q), b2(n+q);
	int ans[q], total = 0;

	for(auto &i : a){
		if(i[1]<0){
			i[1] += 1e10;
			ans[i[3]] = total - b1.get(0, C(i[1], vals1)-1) - b2.get(0, C(i[2], vals2)-1);
		}else{
			b1.add(C(i[1], vals1));
			b2.add(C(i[2], vals2));
			++total;
		}
	}
	for(int i : ans) cout << i nl;
}

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