99792024-03-22 15:09:27111Szakaszokcpp17Elfogadva 100/100149ms38672 KiB
#include <bits/stdc++.h>
using namespace std;

int f[300001];
int X,Y;

void add(int i,int v){
	for(i++;i<=Y;i+=i&-i){
		f[i]+=v;
	}
}

int get(int i){
	int v=0;
	for(;i;i-=i&-i){
		v+=f[i];
	}
	return v;
}

//#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();
	}
	X=xx.size();
	Y=yy.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);
	}
	int ans=0;
	int ansi=-1;
	for(int i=0;i<X;i++){
		for(int j:s[i]){
			add(y[j],1);
			e[x2[j]].push_back(j);
		}
		for(int j:q[i]){
			int ans1=get(y2[j]+1)-get(y1[j]);
			if(ans1>ans){
				ans=ans1;
				ansi=j;
			}
		}
		for(int j:e[i]){
			add(y[j],-1);
		}
	}
	cout<<ansi+1<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/03ms2104 KiB
2Elfogadva0/028ms9400 KiB
3Elfogadva2/23ms2220 KiB
4Elfogadva2/24ms3056 KiB
5Elfogadva2/26ms3500 KiB
6Elfogadva3/314ms5900 KiB
7Elfogadva3/38ms5104 KiB
8Elfogadva3/320ms7396 KiB
9Elfogadva3/321ms7744 KiB
10Elfogadva4/423ms8556 KiB
11Elfogadva4/428ms10284 KiB
12Elfogadva4/445ms14712 KiB
13Elfogadva7/752ms15676 KiB
14Elfogadva7/765ms17804 KiB
15Elfogadva7/778ms20464 KiB
16Elfogadva7/7148ms38672 KiB
17Elfogadva7/748ms14684 KiB
18Elfogadva7/778ms20456 KiB
19Elfogadva7/7109ms30872 KiB
20Elfogadva7/7149ms38552 KiB
21Elfogadva7/7148ms38584 KiB
22Elfogadva7/771ms34044 KiB