oj.uz

Submission #885567

# Submission time Handle Problem Language Result Execution time Memory
885567 2023-12-10T07:40:53 Z serifefedartar trapezoid (balkan11_trapezoid) C++17
24 / 100
 112 ms 55312 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
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 20056 KB Partially correct
2 Partially correct 5 ms 20060 KB Partially correct
3 Partially correct 5 ms 20056 KB Partially correct
4 Partially correct 6 ms 20056 KB Partially correct
5 Partially correct 7 ms 20312 KB Partially correct
6 Partially correct 9 ms 20828 KB Partially correct
7 Partially correct 10 ms 20828 KB Partially correct
8 Partially correct 12 ms 20824 KB Partially correct
9 Partially correct 16 ms 21272 KB Partially correct
10 Partially correct 26 ms 22492 KB Partially correct
11 Partially correct 31 ms 23000 KB Partially correct
12 Runtime error 61 ms 45008 KB Execution killed with signal 11
13 Incorrect 72 ms 26576 KB Output isn't correct
14 Runtime error 92 ms 46540 KB Execution killed with signal 11
15 Runtime error 96 ms 53596 KB Execution killed with signal 11
16 Runtime error 105 ms 55312 KB Execution killed with signal 11
17 Runtime error 94 ms 48592 KB Execution killed with signal 11
18 Partially correct 105 ms 29504 KB Partially correct
19 Runtime error 100 ms 51412 KB Execution killed with signal 11
20 Runtime error 112 ms 50632 KB Execution killed with signal 11