oj.uz

Submission #885566

# Submission time Handle Problem Language Result Execution time Memory
885566 2023-12-10T07:40:20 Z serifefedartar trapezoid (balkan11_trapezoid) C++17
18 / 100
 96 ms 32460 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 = 2e5 + 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
18.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 11096 KB Partially correct
2 Partially correct 2 ms 11100 KB Partially correct
3 Partially correct 3 ms 11100 KB Partially correct
4 Partially correct 3 ms 11188 KB Partially correct
5 Partially correct 4 ms 11356 KB Partially correct
6 Partially correct 5 ms 11356 KB Partially correct
7 Partially correct 5 ms 11612 KB Partially correct
8 Partially correct 7 ms 11548 KB Partially correct
9 Partially correct 12 ms 12000 KB Partially correct
10 Runtime error 28 ms 25556 KB Execution killed with signal 11
11 Runtime error 30 ms 25556 KB Execution killed with signal 11
12 Runtime error 52 ms 26436 KB Execution killed with signal 11
13 Runtime error 63 ms 29656 KB Execution killed with signal 11
14 Runtime error 69 ms 27596 KB Execution killed with signal 11
15 Runtime error 81 ms 30152 KB Execution killed with signal 11
16 Runtime error 87 ms 31036 KB Execution killed with signal 11
17 Runtime error 84 ms 29384 KB Execution killed with signal 11
18 Runtime error 88 ms 32460 KB Execution killed with signal 11
19 Runtime error 92 ms 31012 KB Execution killed with signal 11
20 Runtime error 96 ms 29900 KB Execution killed with signal 11