Submission #1281138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281138		Jawad_Akbar_JJ	Examination (JOI19_examination)	C++20	100 / 100	271 ms	18680 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define os tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

vector<pair<int, int>> v1, v2, v, Q1, Q5, Q4;
int a[1<<17], b[1<<17], c[1<<17], Ans[1<<19], Ans2[1<<19];

void process1(){
	sort(begin(Q4), end(Q4));
	os st;
	for (int i=0, ind = 0;i<=v1.size();i++){
		while (ind < Q4.size() and (i == v1.size() or Q4[ind].first < v1[i].first))
			Ans2[Q4[ind].second] = i, ind++;
	}
}

void process2(){
	sort(begin(Q5), end(Q5));
	os st;
	for (int i=0, ind = 0;i<=v2.size();i++){
		while (ind < Q5.size() and (i == v2.size() or Q5[ind].first < v2[i].first)){
			auto [vl, id] = Q5[ind++];
			Ans2[id] = st.order_of_key(a[id / 3]);
			Ans2[id - 1] = i;
		}
		if (i < v2.size())
			st.insert(v2[i].second);
	}
}

void process3(){
	sort(begin(Q1), end(Q1));
	os stx, sty;

	for (int i=0, ind = 0;i<=v.size();i++){
		while (ind < Q1.size() and (i == v.size() or v[i].first > Q1[ind].first)){
			auto [vl, id] = Q1[ind++];
			Ans[id - 2] = stx.size() - stx.order_of_key(a[id / 3]);
			Ans[id - 1] = sty.size() - sty.order_of_key(b[id / 3]);
			Ans[id - 0] = stx.size();
			// cout<<vl<<" "<<id / 3<<" "<<Ans[id - 2]<<" "<<Ans[id - 1]<<" "<<Ans[id]<<endl;
		}

		if (i != v.size()){
			// cout<<v[i].first<<" "<<v[i].second<<" "<<v[i].first - v[i].second<<endl;
			stx.insert(v[i].second), sty.insert(v[i].first - v[i].second);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin>>n>>m;

	for (int i=1, x, y;i<=n;i++){
		cin>>x>>y;

		v1.push_back({x, y});
		v2.push_back({y, x});
		v.push_back({x + y, x});
	}

	sort(begin(v1), end(v1));
	sort(begin(v2), end(v2));
	sort(begin(v), end(v));
	// return 0;

	for (int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i];

		Q4.push_back({a[i]-1, i * 3 - 2});
		Q5.push_back({b[i]-1, i * 3 - 0});

		Q1.push_back({c[i]-1, i * 3});
	}
	process1();
	process2();
	process3();
	// return 0;

	// for (int i=1;i<=m * 3;i++){
	// 	cout<<Ans2[i]<<' ';
	// 	if (i % 3 == 0)
	// 		cout<<'\n';
	// }
	// cout<<endl;
	// for (int i=1;i<=m * 3;i++){
	// 	cout<<Ans[i]<<' ';
	// 	if (i % 3 == 0)
	// 		cout<<'\n';
	// }
	// cout<<endl;


	for (int i=1;i<=m;i++){
		int A = Ans[3 * i - 2] + Ans[3 * i - 1] + Ans2[i * 3] - Ans[i * 3];
		int B = Ans2[i * 3 - 2] + Ans2[i * 3 - 1] - Ans2[i * 3];
		// cout<<i<<" "<<A<<" "<<B<<' ';
		if (a[i] + b[i] <= c[i])
			cout<<n - A - B<<'\n';
		else
			cout<<n - B<<'\n';
	}
}

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