oj.uz

Submission #885571

# Submission time Handle Problem Language Result Execution time Memory
885571 2023-12-10T07:53:28 Z serifefedartar trapezoid (balkan11_trapezoid) C++17
40 / 100
 123 ms 30412 KB 
#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 = 1e9 + 7;
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];
int fen[MAXN], dp[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;
}

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]);
		}
	}
	cout << mx << " 0" << "\n";
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 20060 KB Partially correct
2 Partially correct 5 ms 20060 KB Partially correct
3 Partially correct 6 ms 20240 KB Partially correct
4 Partially correct 6 ms 20060 KB Partially correct
5 Partially correct 7 ms 20316 KB Partially correct
6 Partially correct 8 ms 20368 KB Partially correct
7 Partially correct 9 ms 20368 KB Partially correct
8 Partially correct 10 ms 20664 KB Partially correct
9 Partially correct 15 ms 21468 KB Partially correct
10 Partially correct 23 ms 22236 KB Partially correct
11 Partially correct 30 ms 22872 KB Partially correct
12 Partially correct 57 ms 25552 KB Partially correct
13 Partially correct 68 ms 26576 KB Partially correct
14 Partially correct 86 ms 27588 KB Partially correct
15 Partially correct 94 ms 28048 KB Partially correct
16 Partially correct 103 ms 28556 KB Partially correct
17 Partially correct 107 ms 29088 KB Partially correct
18 Partially correct 97 ms 29388 KB Partially correct
19 Partially correct 108 ms 29916 KB Partially correct
20 Partially correct 123 ms 30412 KB Partially correct