99762024-03-22 15:01:15111Szakaszokcpp17Időlimit túllépés 72/100211ms51696 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//#define int long long

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("be2.txt","r",stdin);
//	freopen("out.txt","w",stdout);
#endif
	int M,N;
	cin>>M>>N;
	vector<int>x1(M),x2(M),y(M),x(N),y1(N),y2(N);
	vector<int>xx,yy;
	for(int i=0;i<M;i++){
		cin>>x1[i]>>x2[i]>>y[i];
		xx.push_back(x1[i]);
		xx.push_back(x2[i]);
		yy.push_back(y[i]);
	}
	for(int i=0;i<N;i++){
		cin>>x[i]>>y1[i]>>y2[i];
		xx.push_back(x[i]);
		yy.push_back(y1[i]);
		yy.push_back(y2[i]);
	}
	sort(xx.begin(),xx.end());
	sort(yy.begin(),yy.end());
	for(int i=0;i<M;i++){
		x1[i]=lower_bound(xx.begin(),xx.end(),x1[i])-xx.begin();
		x2[i]=lower_bound(xx.begin(),xx.end(),x2[i])-xx.begin();
		y[i]=lower_bound(yy.begin(),yy.end(),y[i])-yy.begin();
	}
	for(int i=0;i<N;i++){
		x[i]=lower_bound(xx.begin(),xx.end(),x[i])-xx.begin();
		y1[i]=lower_bound(yy.begin(),yy.end(),y1[i])-yy.begin();
		y2[i]=lower_bound(yy.begin(),yy.end(),y2[i])-yy.begin();
	}
	int X=xx.size();
	vector<vector<int>>s(X);
	vector<vector<int>>e(X);
	vector<vector<int>>q(X);
	for(int i=0;i<M;i++){
		s[x1[i]].push_back(i);
	}
	for(int i=0;i<N;i++){
		q[x[i]].push_back(i);
	}
	ordered_set<int>o;
	int ans=0;
	int ansi=-1;
	for(int i=0;i<X;i++){
		for(int j:s[i]){
			o.insert(y[j]);
			e[x2[j]].push_back(j);
		}
		for(int j:q[i]){
			int ans1=o.order_of_key(y2[j]+1)-o.order_of_key(y1[j]);
			if(ans1>ans){
				ans=ans1;
				ansi=j;
			}
		}
		for(int j:e[i]){
			o.erase(y[j]);
		}
	}
	cout<<ansi+1<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base72/100
1Elfogadva0/03ms1892 KiB
2Elfogadva0/035ms10000 KiB
3Elfogadva2/23ms3056 KiB
4Elfogadva2/24ms3844 KiB
5Elfogadva2/27ms4700 KiB
6Elfogadva3/317ms7036 KiB
7Elfogadva3/38ms6652 KiB
8Elfogadva3/324ms9332 KiB
9Elfogadva3/326ms10080 KiB
10Elfogadva4/428ms10952 KiB
11Elfogadva4/435ms13024 KiB
12Elfogadva4/457ms18540 KiB
13Elfogadva7/761ms19340 KiB
14Elfogadva7/776ms22720 KiB
15Elfogadva7/790ms26608 KiB
16Időlimit túllépés0/7209ms48240 KiB
17Elfogadva7/759ms24116 KiB
18Elfogadva7/793ms31036 KiB
19Időlimit túllépés0/7153ms44572 KiB
20Időlimit túllépés0/7211ms51696 KiB
21Időlimit túllépés0/7172ms32672 KiB
22Elfogadva7/7104ms50656 KiB