10818 2024. 04. 15 19:04:21 CzDani Szakaszok cpp17 Időlimit túllépés 10/100 248ms 42540 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 10/100
1 Elfogadva 0/0 3ms 1816 KiB
2 Időlimit túllépés 0/0 200ms 3116 KiB
3 Időlimit túllépés 0/2 160ms 1756 KiB
4 Időlimit túllépés 0/2 172ms 2372 KiB
5 Időlimit túllépés 0/2 240ms 2800 KiB
6 Időlimit túllépés 0/3 157ms 3552 KiB
7 Elfogadva 3/3 12ms 5092 KiB
8 Időlimit túllépés 0/3 238ms 4652 KiB
9 Időlimit túllépés 0/3 248ms 4952 KiB
10 Időlimit túllépés 0/4 168ms 5348 KiB
11 Időlimit túllépés 0/4 185ms 5940 KiB
12 Időlimit túllépés 0/4 245ms 8148 KiB
13 Időlimit túllépés 0/7 170ms 9676 KiB
14 Időlimit túllépés 0/7 248ms 11340 KiB
15 Időlimit túllépés 0/7 174ms 14664 KiB
16 Időlimit túllépés 0/7 165ms 21932 KiB
17 Időlimit túllépés 0/7 170ms 14288 KiB
18 Időlimit túllépés 0/7 166ms 18876 KiB
19 Időlimit túllépés 0/7 178ms 20348 KiB
20 Időlimit túllépés 0/7 173ms 27312 KiB
21 Időlimit túllépés 0/7 181ms 29428 KiB
22 Elfogadva 7/7 140ms 42540 KiB