Submission #885624

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885624	2023-12-10T10:26:44 Z	serifefedartar	trapezoid (balkan11_trapezoid)	C++17	100 / 100	156 ms	42560 KB

trapezoid

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 30013;
const ll LOGN = 21;
const ll MAXN = 4e5 + 100;

struct T {
	int a, b, c, d;
	void read() {
		cin >> a >> b >> c >> d;
	}
	T() { }
};
vector<T> trap;
vector<int> cc, in[MAXN], out[MAXN], x[MAXN];
int fen[MAXN], dp[MAXN], ways[MAXN];
void add(int k, int val) {
	while (k < MAXN) {
		fen[k] = max(fen[k], val);
		k += k & -k;
	}
}

int query(int k) {
	int mx = 0;
	while (k) {
		mx = max(mx, fen[k]);
		k -= k & -k;
	}
	return mx;
}

void addS(int k, int val) {
	while (k < MAXN) {
		fen[k] += val;
		fen[k] %= MOD;
		k += k & -k;
	}
}

void setS(int k, int val) {
	while (k < MAXN) {
		fen[k] = val;
		k += k & -k;
	}
}

int queryS(int k) {
	int sum = 0;
	while (k) {
		sum += fen[k];
		sum %= MOD;
		k -= k & -k;
	}
	return sum;
}

int main() {
	fast
	int N;
	cin >> N;

	trap = vector<T>(N);
	for (int i = 0; i < N; i++) {
		trap[i].read();
		cc.push_back(trap[i].a);
		cc.push_back(trap[i].b);
		cc.push_back(trap[i].c);
		cc.push_back(trap[i].d);
	}
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	for (auto &u : trap) {
		u.a = upper_bound(cc.begin(), cc.end(), u.a) - cc.begin();
		u.b = upper_bound(cc.begin(), cc.end(), u.b) - cc.begin();
		u.c = upper_bound(cc.begin(), cc.end(), u.c) - cc.begin();
		u.d = upper_bound(cc.begin(), cc.end(), u.d) - cc.begin();
	}
	for (int i = 0; i < N; i++) {
		in[trap[i].a].push_back(i);
		out[trap[i].b].push_back(i);
	}

	int mx = 0;
	for (int i = 1; i < MAXN; i++) {
		for (auto u : out[i])
			add(trap[u].d, dp[u]);
		for (auto u : in[i]) {
			int Q = query(trap[u].c);
			dp[u] = Q + 1;
			mx = max(mx, dp[u]);
		}
	}

	for (int i = 0; i < N; i++) {
		x[dp[i]].push_back(i);
	}
	memset(fen, 0, sizeof(fen));
	for (int i = 0; i < MAXN; i++)
		in[i].clear(), out[i].clear();

	for (auto u : x[1])
		ways[u] = 1;

	int ans = x[1].size();
	for (int i = 2; i <= mx; i++) {
		int sum = 0;
		vector<pair<int,int>> v;
		for (auto u : x[i-1])
			v.push_back({trap[u].b, u});
		for (auto u : x[i])
			v.push_back({trap[u].a, u});
		sort(v.begin(), v.end());

		for (auto u : v) {
			if (dp[u.s] == i) {
				ways[u.s] = queryS(trap[u.s].c);
				sum += ways[u.s];
				sum %= MOD;
			} else
				addS(trap[u.s].d, ways[u.s]);
		}

		ans = sum;
		for (auto u : v)
			setS(trap[u.s].d, 0);
	}
	cout << mx << " " << ans << "\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	32092 KB	Output is correct
2	Correct	11 ms	32276 KB	Output is correct
3	Correct	12 ms	32088 KB	Output is correct
4	Correct	12 ms	32344 KB	Output is correct
5	Correct	13 ms	32348 KB	Output is correct
6	Correct	14 ms	32348 KB	Output is correct
7	Correct	14 ms	32604 KB	Output is correct
8	Correct	16 ms	32604 KB	Output is correct
9	Correct	22 ms	33248 KB	Output is correct
10	Correct	35 ms	34268 KB	Output is correct
11	Correct	43 ms	34900 KB	Output is correct
12	Correct	73 ms	37428 KB	Output is correct
13	Correct	98 ms	38512 KB	Output is correct
14	Correct	129 ms	39412 KB	Output is correct
15	Correct	123 ms	39988 KB	Output is correct
16	Correct	130 ms	40400 KB	Output is correct
17	Correct	133 ms	40832 KB	Output is correct
18	Correct	128 ms	41420 KB	Output is correct
19	Correct	136 ms	41916 KB	Output is correct
20	Correct	156 ms	42560 KB	Output is correct