oj.uz

Submission #885563

# Submission time Handle Problem Language Result Execution time Memory
885563 2023-12-10T07:29:03 Z serifefedartar trapezoid (balkan11_trapezoid) C++17
0 / 100
 98 ms 35532 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].c].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[i] = Q + 1;
			mx = max(mx, dp[i]);
		}
	}
	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 10840 KB Output isn't correct
3 Incorrect 3 ms 10904 KB Output isn't correct
4 Incorrect 5 ms 10844 KB Output isn't correct
5 Incorrect 4 ms 11096 KB Output isn't correct
6 Incorrect 5 ms 11356 KB Output isn't correct
7 Incorrect 8 ms 11216 KB Output isn't correct
8 Incorrect 7 ms 11412 KB Output isn't correct
9 Incorrect 11 ms 12000 KB Output isn't correct
10 Runtime error 28 ms 26384 KB Execution killed with signal 11
11 Runtime error 34 ms 27344 KB Execution killed with signal 11
12 Runtime error 51 ms 27856 KB Execution killed with signal 11
13 Runtime error 65 ms 31132 KB Execution killed with signal 11
14 Runtime error 70 ms 29388 KB Execution killed with signal 11
15 Runtime error 81 ms 33480 KB Execution killed with signal 11
16 Runtime error 88 ms 34492 KB Execution killed with signal 11
17 Runtime error 84 ms 31944 KB Execution killed with signal 11
18 Runtime error 85 ms 35532 KB Execution killed with signal 11
19 Runtime error 89 ms 32768 KB Execution killed with signal 11
20 Runtime error 98 ms 33512 KB Execution killed with signal 11