제출 #1281087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281087		Jawad_Akbar_JJ	Examination (JOI19_examination)	C++20	0 / 100	212 ms	15740 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 = {{-1, -1}}, v2 = v1, Q1, Q2, Q3, Q5, Q4;
int a[1<<17], b[1<<17], c[1<<17], Ans[1<<19], Ans2[1<<18];

void process1(){
	sort(begin(Q1), end(Q1));
	sort(begin(Q4), end(Q4));
	os st;
	for (int i=v1.size()-1;i>=0;i--){
		while (Q1.size() > 0 and Q1.back().first > v1[i].first){
			auto [vl, id] = Q1.back();
			Q1.pop_back();
			Ans[id] = st.order_of_key(c[(id + 3) / 4]);
		}
		while (Q4.size() > 0 and Q4.back().first >= v1[i].first)
			Ans2[Q4.back().second] = i, Q4.pop_back();
		st.insert(v1[i].first + v1[i].second);
	}
}

void process2(){
	sort(begin(Q2), end(Q2));
	sort(begin(Q5), end(Q5));
	os st;
	for (int i=v2.size()-1;i>=0;i--){
		while (Q2.size() > 0 and Q2.back().first > v2[i].first){
			auto [vl, id] = Q2.back();
			Q2.pop_back();
			Ans[id] = st.order_of_key(c[(id + 3) / 4]);
		}
		while (Q5.size() > 0 and Q5.back().first >= v2[i].first)
			Ans2[Q5.back().second] = i, Q5.pop_back();
		st.insert(v2[i].first + v2[i].second);
	}
}

void process3(){
	sort(rbegin(Q3), rend(Q3));
	os st;
	for (int i=1;i<=v1.size();i++){
		if (Q3.size() > 0 and (i == v1.size() or Q3.back().first < v1[i].first)){
			auto [vl, id] = Q3.back();
			Q3.pop_back();
			Ans[id] = st.order_of_key(b[(id + 3) / 4]);
		}
		if (i != v1.size())
			st.insert(v1[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});
	}

	sort(begin(v1), end(v1));
	sort(begin(v2), end(v2));

	for (int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i];
		Q1.push_back({a[i], 4 * i - 3});
		Q2.push_back({b[i], 4 * i - 2});
		Q1.push_back({0, 4 * i - 1});
		Q3.push_back({a[i]-1, 4 * i});
		Q4.push_back({a[i] - 1, i * 2 - 1});
		Q5.push_back({b[i] - 1, i * 2});
	}

	process1();
	process2();
	process3();

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

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


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

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