108182024-04-15 19:04:21CzDaniSzakaszokcpp17Time limit exceeded 10/100248ms42540 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct es {
	int x, t, i;
};

bool operator<(es a, es b) {
	if (a.x==b.x) {
		return a.t<b.t;
	}
	return a.x<b.x;
}

int m, n;
int t[2000001];

void update (int v, int tl, int tr, int ind, int val) {
	if (tl==tr) {
		t[v]+=val;
		return;
	} else {
		int mid = (tl+tr)/2;
		if (ind <= mid) {
			update(v*2, tl, mid, ind, val);
		} else {
			update(v*2+1, mid+1, tr, ind, val);
		}
		t[v] = t[v*2] + t[v*2+1];
	}
}

int query(int v, int tl, int tr, int l, int r) {
	if (l > r) return 0;
	if (tl >= l && tr <= r) {
		return t[v];
	}
	int mid = (tl+tr)/2;
	return query(v*2, tl, mid, l, min(r, mid)) + query(v*2+1, mid+1, tr, max(l, mid+1), r);
}

signed main() {
	cin >> m >> n;
	vector<int> vx1(m+1), vx2(m+1), vy(m+1), fy2(n+1), fy1(n+1), fx(n+1), comp;
	//x1:bal x2:jobb y1:also y2:felso

	for (int i = 1; i <= m; i++) {
		cin >> vx1[i] >> vx2[i] >> vy[i];
		comp.push_back(vy[i]);
	}
	for (int i = 1; i <= n; i++) {
		cin >> fx[i] >> fy1[i] >> fy2[i];
		comp.push_back(fy1[i]);
		comp.push_back(fy2[i]);
	}

	sort(comp.begin(), comp.end());
	comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

	for (int i = 1; i <= m; i++) {
		vy[i] = lower_bound(comp.begin(), comp.end(), vy[i]) - comp.begin() + 1;
	}
	for (int i = 1; i <= n; i++) {
		fy1[i] = lower_bound(comp.begin(), comp.end(), fy1[i]) - comp.begin() + 1;
		fy2[i] = lower_bound(comp.begin(), comp.end(), fy2[i]) - comp.begin() + 1;
	}
	/*
	esemeny tipusok:
	1: vsz vonal +
	2: fugg vonal
	3: vsz vonal -
	*/
	vector<es> v;
	for (int i = 1; i <= m; i++) {
		v.push_back({vx1[i], 1, i});
		v.push_back({vx2[i], 3, i});
	}
	for (int i = 1; i <= n; i++) {
		v.push_back({fx[i], 2, i});
	}

	sort(v.begin(), v.end());

	int maxi = -1, ind = 0;

	for (auto x : v) {
		if (x.t == 1) {
			update(1, 1, n, vy[x.i], 1);
		} else if (x.t == 2) {
			int sum = query(1, 1, n, fy1[x.i], fy2[x.i]);
			if (sum > maxi) {
				ind = x.i;
				maxi = sum;
			} else if (maxi == sum) {
				if (x.i < ind) {
					ind = x.i;
				}
			}
		} else if (x.t == 3) {
			update(1, 1, n, vy[x.i], -1);
		}
	}

	cout << ind;
}
SubtaskSumTestVerdictTimeMemory
base10/100
1Accepted0/03ms1816 KiB
2Time limit exceeded0/0200ms3116 KiB
3Time limit exceeded0/2160ms1756 KiB
4Time limit exceeded0/2172ms2372 KiB
5Time limit exceeded0/2240ms2800 KiB
6Time limit exceeded0/3157ms3552 KiB
7Accepted3/312ms5092 KiB
8Time limit exceeded0/3238ms4652 KiB
9Time limit exceeded0/3248ms4952 KiB
10Time limit exceeded0/4168ms5348 KiB
11Time limit exceeded0/4185ms5940 KiB
12Time limit exceeded0/4245ms8148 KiB
13Time limit exceeded0/7170ms9676 KiB
14Time limit exceeded0/7248ms11340 KiB
15Time limit exceeded0/7174ms14664 KiB
16Time limit exceeded0/7165ms21932 KiB
17Time limit exceeded0/7170ms14288 KiB
18Time limit exceeded0/7166ms18876 KiB
19Time limit exceeded0/7178ms20348 KiB
20Time limit exceeded0/7173ms27312 KiB
21Time limit exceeded0/7181ms29428 KiB
22Accepted7/7140ms42540 KiB