제출 #1281140

#제출 시각아이디문제언어결과실행 시간메모리
1281140Jawad_Akbar_JJExamination (JOI19_examination)C++20
100 / 100
251 ms18668 KiB
#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();
		}

		if (i != v.size())
			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));

	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();
	
	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];
		if (a[i] + b[i] <= c[i])
			cout<<n - A - B<<'\n';
		else
			cout<<n - B<<'\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...