Submission #885618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885618	2023-12-10T10:20:48 Z	serifefedartar	trapezoid (balkan11_trapezoid)	C++17	52 / 100	148 ms	42440 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 = max(ans, sum);
		for (auto u : v)
			setS(trap[u.s].d, 0);
	}
	cout << mx << " " << ans << "\n";
}

Subtask #1

52.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	32088 KB	Output is correct
2	Correct	10 ms	32088 KB	Output is correct
3	Partially correct	10 ms	32092 KB	Partially correct
4	Partially correct	11 ms	32280 KB	Partially correct
5	Correct	12 ms	32348 KB	Output is correct
6	Partially correct	13 ms	32348 KB	Partially correct
7	Partially correct	14 ms	32604 KB	Partially correct
8	Correct	16 ms	32860 KB	Output is correct
9	Partially correct	22 ms	33248 KB	Partially correct
10	Partially correct	31 ms	34144 KB	Partially correct
11	Partially correct	43 ms	35020 KB	Partially correct
12	Partially correct	71 ms	37324 KB	Partially correct
13	Partially correct	87 ms	38352 KB	Partially correct
14	Partially correct	113 ms	39332 KB	Partially correct
15	Partially correct	119 ms	39884 KB	Partially correct
16	Partially correct	123 ms	40392 KB	Partially correct
17	Partially correct	129 ms	40900 KB	Partially correct
18	Partially correct	121 ms	41420 KB	Partially correct
19	Partially correct	135 ms	41912 KB	Partially correct
20	Partially correct	148 ms	42440 KB	Partially correct