제출 #348779

#제출 시각아이디문제언어결과실행 시간메모리
348779cheissmart사다리꼴 (balkan11_trapezoid)C++14
5 / 100
140 ms9680 KiB
#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 += b.S;
	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, 0};
	for(; pos; pos -= pos & -pos)
		res = add(res, bit[pos]);
	return res;
}

signed main()
{
	IO_OP;

	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));
	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> 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);
		if(tt.F > 0) {
			tt.F++;
			dp[i] = tt;
		} else {
			dp[i] = {1, 1};
		}
		s.push({b, i});
		ans = add(ans, dp[i]);
	}
	cout << ans.F << " " << ans.S << endl;
}

#Verdict Execution timeMemoryGrader output
Fetching results...