Submission #885624

#	Time	Username	Problem	Language	Result	Execution time	Memory
885624		serifefedartar	trapezoid (balkan11_trapezoid)	C++17	100 / 100	156 ms	42560 KiB

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 / 100