Submission #260030

#	Time	Username	Problem	Language	Result	Execution time	Memory
260030		minhcool	Examination (JOI19_examination)	C++17	2 / 100	102 ms	6332 KiB

examination

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define er erase
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
const int N = 1e5 + 5;
 
int n, q, BIT[N], ans[N];
iii queries[N];
ii students[N];
 
void update(int u){
	for(; u <= 100001 && u; u += (u & -u)){
		//cout << u << " " << u + (u & -u) << "\n";
		++BIT[u];
	}
}
 
int get(int u){
	if(u < 0) return 0;
	int sum = 0;
	for(; u; u -= (u & -u)) sum += BIT[u];
	return sum;
}
 
bool cmp(iii a, iii b){
	if(a.fi != b.fi) return a.fi > b.fi;
	return 0;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("examination_19.inp", "r", stdin);
	//freopen("examination_19.out", "w", stdout);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> students[i].fi >> students[i].se;
		++students[i].fi;
		++students[i].se;
	}
	sort(students + 1, students + n + 1, greater<ii>());
	if(n <= 3000 && q <= 3000){
		while(q--){
			int x, y, z, ans = 0;
			cin >> x >> y >> z;
			++x;
			++y;
			z += 2;
			for(int i = 1; i <= n; i++) ans += (x <= students[i].fi && y <= students[i].se && z <= (students[i].fi + students[i].se));
			cout << ans << "\n";
		}
	}
	else{
		for(int i = 1; i <= q; i++){
			//cout << i << "\n";
			int z;
			cin >> queries[i].fi.fi >> queries[i].fi.se >> z;
			++queries[i].fi.fi;
			++queries[i].fi.se;
			queries[i].se = i;
		}
		sort(queries + 1, queries + q + 1, cmp);
		int itr = 1;
		for(int i = 1; i <= q; i++){
			//cout << i << "\n";
			while(itr <= n && students[itr].fi >= queries[i].fi.fi){
				update(students[itr].se);
				++itr;
				//cout << itr << "\n";
			}
			ans[queries[i].se] = get(100002) - get(queries[i].fi.se - 1);
		}
		for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
	}
}
 

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