Submission #1242043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242043		MateiKing80	trapezoid (balkan11_trapezoid)	C++20	100 / 100	318 ms	40840 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 1e5 + 5, mod = 30013;

pair<int, int> aib[4 * N];

int lsb(int x) {
	return x & -x;
}

pii add(pii a, pii b) {
	if (a.fr > b.fr)
		return a;
	if (a.fr < b.fr)
		return b;
	return {a.fr, (a.sc + b.sc) % mod};
}

void update(int pos, pii x) {
	while (pos < 4 * N) {
		aib[pos] = add(x, aib[pos]);
		pos += lsb(pos);
	}
}

pii query(int pos) {
	pii ans = {0, 1};
	while (pos) {
		ans = add(ans, aib[pos]);
		pos -= lsb(pos);
	}
	return ans;
}

struct Trapez {
	int a, b, c, d, i;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Trapez> v;
	map<int, int> mp, remp;
	for (int i = 1; i <= n; i ++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		mp[a] ++, mp[b] ++, mp[c] ++, mp[d] ++;
		v.push_back({a, b, c, d, i});
	}
	int cnt = 0;
	for (auto i : mp)
		remp[i.fr] = ++cnt;
	for (auto &i : v) {
		i.a = remp[i.a];
		i.b = remp[i.b];
		i.c = remp[i.c];
		i.d = remp[i.d];
	}
	auto vq = v;
	auto vu = v;
	sort(vq.begin(), vq.end(), [&] (Trapez a, Trapez b) {return a.c < b.c;});
	sort(vu.begin(), vu.end(), [&] (Trapez a, Trapez b) {return a.d < b.d;});
	vector<pii> ans(n + 1);
	int loc = 0;
	for (auto i : vq) {
		while (loc < (int)vu.size() && vu[loc].d < i.c) {
			update(vu[loc].b, ans[vu[loc].i]);
			loc ++;
		}
		ans[i.i] = query(i.a - 1);
		ans[i.i].fr ++;
	}
	pii rasp = {0, 0};
	for (auto i : ans)
		rasp = add(rasp, i);
	cout << rasp.fr << " " << rasp.sc << '\n';
}

• Subtask 1: 100 / 100