oj.uz

Submission #101696

# Submission time Handle Problem Language Result Execution time Memory
101696 2019-03-19T13:50:32 Z KCSC Exhibition (JOI19_ho_t2) C++14
0 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;

int frm[DIM], stk[DIM];
pair<int, int> pic[DIM];

int main(void) {
#ifdef HOME
	freopen("exhibition.in", "r", stdin);
	freopen("exhibition.out", "w", stdout);
#endif
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> pic[i].first >> pic[i].second; }
	for (int i = 1; i <= m; ++i) {
		cin >> frm[i]; }
	sort(pic + 1, pic + n + 1);
	sort(frm + 1, frm + m + 1);
	int le1 = 1, ri1 = m; 
	while (le1 <= ri1) {
		int md1 = (le1 + ri1) >> 1, sz = 0;
		for (int i = 1; i <= n and sz < md1; ++i) {
			if ((!sz or pic[i].second >= pic[stk[sz]].second) and pic[i].first <= frm[m - md1 + sz + 1]) {
				stk[++sz] = i; }
			else {
				int le2 = 1, ri2 = sz;
				while (le2 <= ri2) {
					int md2 = (le2 + ri2) >> 1;
					if ((md2 == 1 or pic[i].second >= pic[stk[md2 - 1]].second) and pic[i].first <= frm[m - md1 + md2]) {
						le2 = md2 + 1; }
					else {
						ri2 = md2 - 1; } }
				if (ri2 != 0 and pic[stk[ri2]].second > pic[i].second) {
					stk[ri2] = i; } } }
		if (sz == md1) {
			le1 = md1 + 1; }
		else {
			ri1 = md1 - 1; } }
	cout << ri1;
	return 0; }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -