oj.uz

Submission #348785

# Submission time Handle Problem Language Result Execution time Memory
348785 2021-01-15T17:22:55 Z cheissmart trapezoid (balkan11_trapezoid) C++14
100 / 100
 160 ms 12624 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8172 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 5 ms 8172 KB Output is correct
4 Correct 5 ms 8300 KB Output is correct
5 Correct 7 ms 8300 KB Output is correct
6 Correct 8 ms 8428 KB Output is correct
7 Correct 9 ms 8556 KB Output is correct
8 Correct 11 ms 8556 KB Output is correct
9 Correct 18 ms 9064 KB Output is correct
10 Correct 30 ms 9448 KB Output is correct
11 Correct 39 ms 9568 KB Output is correct
12 Correct 78 ms 10584 KB Output is correct
13 Correct 93 ms 10968 KB Output is correct
14 Correct 109 ms 11756 KB Output is correct
15 Correct 123 ms 11736 KB Output is correct
16 Correct 133 ms 11856 KB Output is correct
17 Correct 136 ms 11984 KB Output is correct
18 Correct 124 ms 12240 KB Output is correct
19 Correct 145 ms 12368 KB Output is correct
20 Correct 160 ms 12624 KB Output is correct