oj.uz

Submission #885565

# Submission time Handle Problem Language Result Execution time Memory
885565 2023-12-10T07:33:29 Z serifefedartar trapezoid (balkan11_trapezoid) C++17
0 / 100
 97 ms 33540 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;
int fen[MAXN], dp[MAXN];
vector<int> in[MAXN], out[MAXN];
void add(int k, int val) {
	while (k) {
		fen[k] = max(fen[k], val);
		k -= k & -k;
	}
}

int query(int k) {
	int mx = 0;
	while (k < MAXN) {
		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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Incorrect 3 ms 10868 KB Output isn't correct
4 Incorrect 3 ms 10840 KB Output isn't correct
5 Incorrect 4 ms 10840 KB Output isn't correct
6 Incorrect 5 ms 11120 KB Output isn't correct
7 Incorrect 5 ms 11096 KB Output isn't correct
8 Incorrect 7 ms 11352 KB Output isn't correct
9 Incorrect 11 ms 11744 KB Output isn't correct
10 Runtime error 27 ms 25776 KB Execution killed with signal 11
11 Runtime error 32 ms 26876 KB Execution killed with signal 11
12 Runtime error 51 ms 26416 KB Execution killed with signal 11
13 Runtime error 69 ms 33540 KB Execution killed with signal 11
14 Runtime error 68 ms 27848 KB Execution killed with signal 11
15 Runtime error 83 ms 31436 KB Execution killed with signal 11
16 Runtime error 91 ms 32596 KB Execution killed with signal 11
17 Runtime error 85 ms 29832 KB Execution killed with signal 11
18 Runtime error 84 ms 33040 KB Execution killed with signal 11
19 Runtime error 91 ms 31172 KB Execution killed with signal 11
20 Runtime error 97 ms 30836 KB Execution killed with signal 11