99772024-03-22 15:04:34111Szakaszokcpp17Wrong answer 62/100152ms44072 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>;

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&-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;
}
SubtaskSumTestVerdictTimeMemory
base62/100
1Accepted0/03ms2112 KiB
2Accepted0/028ms9840 KiB
3Accepted2/23ms2924 KiB
4Accepted2/24ms3760 KiB
5Accepted2/26ms4360 KiB
6Accepted3/314ms6708 KiB
7Accepted3/38ms5824 KiB
8Wrong answer0/320ms8676 KiB
9Accepted3/324ms9588 KiB
10Accepted4/424ms10564 KiB
11Accepted4/428ms12784 KiB
12Accepted4/445ms18132 KiB
13Wrong answer0/752ms19524 KiB
14Wrong answer0/765ms22944 KiB
15Wrong answer0/778ms25652 KiB
16Accepted7/7149ms44072 KiB
17Accepted7/746ms20148 KiB
18Wrong answer0/778ms25800 KiB
19Accepted7/7111ms36228 KiB
20Accepted7/7149ms43816 KiB
21Time limit exceeded0/7152ms25984 KiB
22Accepted7/771ms39548 KiB