Submission #935612

#	Time	Username	Problem	Language	Result	Execution time	Memory
935612		yellowtoad	Examination (JOI19_examination)	C++17	0 / 100	1979 ms	25152 KiB

examination

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#define f first
#define s second
#define int long long
using namespace std;

const int sz = sqrt(1e5);
int n, test, cur = 1, ans[100010], l, r, mid, pos;
pair<int,int> a[100010], b[100010], grp[100010];
vector<vector<int>> v, vv;
pair<pair<int,int>,pair<int,int>> query[100010];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> test;
	for (int i = 1; i <= n; i++) cin >> a[i].f >> a[i].s;
	sort(a+1,a+n+1);
	for (int i = 1; i <= n; i++) b[i] = {a[i].f+a[i].s,i};
	sort(b+1,b+n+1,greater<pair<int,int>>());
	for (int i = 1; i <= test; i++) {
		cin >> query[i].s.f >> query[i].s.s >> query[i].f.f;
		query[i].f.s = i;
	}
	sort(query+1,query+test+1,greater<pair<pair<int,int>,pair<int,int>>>());
	for (int i = 1; i <= n; i++) {
		if (i%sz == 1) v.push_back({}), vv.push_back({});
		v.back().push_back(-1);
		vv.back().push_back(-1);
		grp[i] = {v.size()-1,v.back().size()-1};
	}
	for (int i = 1; i <= test; i++) {
		while (b[cur].f >= query[i].f.f) {
			vv[grp[b[cur].s].f][grp[b[cur].s].s] = a[b[cur].s].s;
			for (int j = 0; j < v[grp[b[cur].s].f].size(); j++) v[grp[b[cur].s].f][j] = vv[grp[b[cur].s].f][j];
			sort(v[grp[b[cur].s].f].begin(),v[grp[b[cur].s].f].end());
			cur++;
		}
		l = 1; r = n;
		while (l <= r) {
			mid = (l+r)/2;
			if (a[mid].f >= query[i].s.f) r = mid-1;
			else l = mid+1;
		}
		pos = l;
		int cnt = 0;
		if (l == n+1) continue;
		for (int j = grp[pos].s; j < v[grp[pos].f].size(); j++) if (vv[grp[pos].f][j] >= query[i].s.s) cnt++;
		for (int j = grp[pos].f+1; j < v.size(); j++) {
			l = 0; r = v[j].size()-1;
			while (l <= r) {
				mid = (l+r)/2;
				if (v[j][mid] < query[i].s.s) l = mid+1;
				else r = mid-1;
			}
			cnt += v[j].size()-l;
		}
		ans[query[i].f.s] = cnt;
	}
	for (int i = 1; i <= test; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:38:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for (int j = 0; j < v[grp[b[cur].s].f].size(); j++) v[grp[b[cur].s].f][j] = vv[grp[b[cur].s].f][j];
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:51:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int j = grp[pos].s; j < v[grp[pos].f].size(); j++) if (vv[grp[pos].f][j] >= query[i].s.s) cnt++;
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:52:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j = grp[pos].f+1; j < v.size(); j++) {
      |                              ~~^~~~~~~~~~

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