Submission #260026

#	Time	Username	Problem	Language	Result	Execution time	Memory
260026		minhcool	Examination (JOI19_examination)	C++17	0 / 100	2 ms	384 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 <= 100000; u += (u & -u)) ++BIT[u];
}

int get(int u){
	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;
	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;
			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++){
			int z;
			cin >> queries[i].fi.fi >> queries[i].fi.se >> z;
			queries[i].se = i;
		}
		sort(queries + 1, queries + q + 1, cmp);
		int itr = 1;
		for(int i = 1; i <= q; i++){
			while(itr <= n && students[itr].fi >= queries[i].fi.fi){
				update(students[itr].se);
				++itr;
			}
			ans[queries[i].se] = get(100000) - get(queries[i].fi.se - 1);
		}
		for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("examination_19.inp", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("examination_19.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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