Submission #885617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885617	2023-12-10T10:19:26 Z	serifefedartar	trapezoid (balkan11_trapezoid)	C++17	46 / 100	148 ms	44100 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;
		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];
		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];
			} 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

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	32088 KB	Output is correct
2	Correct	10 ms	32092 KB	Output is correct
3	Partially correct	10 ms	32088 KB	Partially correct
4	Partially correct	11 ms	32344 KB	Partially correct
5	Partially correct	12 ms	32348 KB	Partially correct
6	Partially correct	13 ms	32816 KB	Partially correct
7	Partially correct	17 ms	32656 KB	Partially correct
8	Partially correct	16 ms	32860 KB	Partially correct
9	Partially correct	21 ms	33328 KB	Partially correct
10	Partially correct	31 ms	34768 KB	Partially correct
11	Partially correct	45 ms	35344 KB	Partially correct
12	Partially correct	71 ms	38380 KB	Partially correct
13	Partially correct	86 ms	39376 KB	Partially correct
14	Partially correct	102 ms	40648 KB	Partially correct
15	Partially correct	115 ms	41264 KB	Partially correct
16	Partially correct	123 ms	41936 KB	Partially correct
17	Partially correct	129 ms	42608 KB	Partially correct
18	Partially correct	119 ms	42956 KB	Partially correct
19	Partially correct	131 ms	43452 KB	Partially correct
20	Partially correct	148 ms	44100 KB	Partially correct