99782024-03-22 15:06:23111Szakaszokcpp17Hibás válasz 69/100149ms38884 KiB
#include <bits/stdc++.h>
using namespace std;

int f[300001];
int X;

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

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

//#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();
	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
base69/100
1Elfogadva0/03ms1836 KiB
2Elfogadva0/028ms9336 KiB
3Elfogadva2/23ms2412 KiB
4Elfogadva2/24ms3200 KiB
5Elfogadva2/26ms3900 KiB
6Elfogadva3/314ms6256 KiB
7Elfogadva3/38ms5420 KiB
8Hibás válasz0/320ms7708 KiB
9Elfogadva3/323ms8308 KiB
10Elfogadva4/423ms8824 KiB
11Elfogadva4/428ms10396 KiB
12Elfogadva4/443ms14876 KiB
13Hibás válasz0/752ms15432 KiB
14Hibás válasz0/764ms17816 KiB
15Hibás válasz0/776ms20440 KiB
16Elfogadva7/7148ms38564 KiB
17Elfogadva7/746ms14628 KiB
18Hibás válasz0/778ms20508 KiB
19Elfogadva7/7109ms31016 KiB
20Elfogadva7/7148ms38884 KiB
21Elfogadva7/7149ms38756 KiB
22Elfogadva7/771ms34104 KiB