Submission #348785

#	Time	Username	Problem	Language	Result	Execution time	Memory
348785		cheissmart	trapezoid (balkan11_trapezoid)	C++14	100 / 100	160 ms	12624 KiB

trapezoid

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, M = 30013, N = 1e6 + 7;

pi dp[N];
pi bit[N];

pi add(pi a, pi b) {
	if(a.F > b.F) return a;
	else if(a.F < b.F) return b;
	a.S = (a.S + b.S) % M;
	return a;
}

void add(int pos, pi val) {
	for(; pos < N; pos += pos & -pos)
		bit[pos] = add(bit[pos], val);
}

pi qry(int pos) {
	pi res = {0, 1};
	for(; pos; pos -= pos & -pos)
		res = add(res, bit[pos]);
	return res;
}

signed main()
{
	IO_OP;

	memset(bit, -1, sizeof bit);
	mt19937 rng(time(0));

	int n;
	cin >> n;
	V<array<int, 4>> v;
	vi compress;
	for(int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v.PB({a, b, c, d});
		for(int j = 0; j < 4; j++)
			compress.PB(v[i][j]);
	}
	sort(ALL(compress));
	compress.resize(unique(ALL(compress)) - compress.begin());
	for(int i = 0; i < n; i++)
		for(int j = 0; j < 4; j++)
			v[i][j] = lower_bound(ALL(compress), v[i][j]) - compress.begin() + 1;
	sort(ALL(v));
	priority_queue<pi, V<pi>, greater<pi>> s; // {r, i}
	pi ans = {0, 0};
	for(int i = 0; i < n; i++) {
		int a = v[i][0], b = v[i][1], c = v[i][2];
		while(s.size() && s.top().F < a) {
			int j = s.top().S;
			s.pop();
			add(v[j][3], dp[j]);
		}
		pi tt = qry(c - 1);
		tt.F++;
		dp[i] = tt;
		s.push({b, i});
		ans = add(ans, dp[i]); 
	}
	cout << ans.F << " " << ans.S << endl;
}

• Subtask 1: 100 / 100