9979 2024. 03. 22 15:09:27 111 Szakaszok cpp17 Elfogadva 100/100 149ms 38672 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 Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 2104 KiB
2 Elfogadva 0/0 28ms 9400 KiB
3 Elfogadva 2/2 3ms 2220 KiB
4 Elfogadva 2/2 4ms 3056 KiB
5 Elfogadva 2/2 6ms 3500 KiB
6 Elfogadva 3/3 14ms 5900 KiB
7 Elfogadva 3/3 8ms 5104 KiB
8 Elfogadva 3/3 20ms 7396 KiB
9 Elfogadva 3/3 21ms 7744 KiB
10 Elfogadva 4/4 23ms 8556 KiB
11 Elfogadva 4/4 28ms 10284 KiB
12 Elfogadva 4/4 45ms 14712 KiB
13 Elfogadva 7/7 52ms 15676 KiB
14 Elfogadva 7/7 65ms 17804 KiB
15 Elfogadva 7/7 78ms 20464 KiB
16 Elfogadva 7/7 148ms 38672 KiB
17 Elfogadva 7/7 48ms 14684 KiB
18 Elfogadva 7/7 78ms 20456 KiB
19 Elfogadva 7/7 109ms 30872 KiB
20 Elfogadva 7/7 149ms 38552 KiB
21 Elfogadva 7/7 148ms 38584 KiB
22 Elfogadva 7/7 71ms 34044 KiB