Submission #1271533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271533		WH8	Examination (JOI19_examination)	C++20	100 / 100	782 ms	471272 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cerr << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

struct node {
	int s, e, m, v;
	node *l = nullptr, *r = nullptr;
	node (int a, int b){
		s = a, e = b, m = (s + e) / 2, v = 0;
	}
	void create(){
		if (l == nullptr){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int x, int nv){
		if (s == e) {
			v += nv;
			return;
		}
		create();
		if (x <= m) l->update(x, nv);
		else r->update(x, nv);
		v = r->v + l->v;
	}
	int query(int a){ // sum 0 to a;
		if (a == -1) return 0;
		if (s == e) return v;
		create();
		if (a > m) return l->v + r->query(a);
		else return l->query(a);
	}
};

int32_t main(){
	FASTIO
	int n, q; cin >> n >> q;
	vector<pll> v(n); iloop(0, n) cin >> v[i].f >> v[i].s;
	sort(all(v), [&](pll a, pll b){
		return a.f + a.s < b.f + b.s;
	});
	int sptr = 0;
	int ans[q];
	vector<pair<iii, int>> qs;
	iloop(0, q){
		int x, y, z; cin >> x >> y >> z;
		qs.pb({{x, y, max(x + y, z)}, i});
	}
	sort(all(qs), [&](auto a, auto b){
		return g2(a.f) < g2(b.f);
	});
	node * mr = new node(0, 1e9 + 5);
	node * ir = new node(0, 1e9 + 5);
	iloop(0, n){
		mr->update(v[i].f, 1);
		ir->update(v[i].s, 1);
	}
	int cans = n;
	//for (auto it : v) cout << it.f << " " << it.s << "|";
	iloop(0, q){
		int x = g0(qs[i].f), y = g1(qs[i].f), z = g2(qs[i].f), ind = qs[i].s;
		//cout << "X Y Z IND : " << x << " " << y << " " << z << " " << ind << endl;
		while (sptr < n and v[sptr].f + v[sptr].s < z){
			mr->update(v[sptr].f, -1);
			ir->update(v[sptr].s, -1);
			sptr++;
			cans--;
		}
		int belx = mr->query(x-1);
		int bely = ir->query(y-1);
		ans[ind] = cans - belx - bely;
	}
	iloop(0, q) cout << ans[i] << endl;
}

Compilation message (stderr)

examination.cpp: In function 'int32_t main()':
examination.cpp:71:47: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   71 |                 qs.pb({{x, y, max(x + y, z)}, i});
      |                                               ^

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