oj.uz

Submission #121073

# Submission time Handle Problem Language Result Execution time Memory
121073 2019-06-26T04:44:21 Z 윤교준(#2970) Exhibition (JOI19_ho_t2) C++14
0 / 100
 7 ms 3584 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MAXM = 100055;
const int MX = 131072;

struct SEG {
	SEG() { init(); }
	pii dc[MX*2];
	int di[MX*2];

	void init() {
		fill(dc, dc+MX*2, pii(-INF, INF));
		fill(di, di+MX*2, -1);
	}
	void upd(int x, int cnt, int height, int idx) {
		pii r(cnt, -height);
		x += MX;
		if(dc[x] < r) {
			dc[x] = r;
			di[x] = idx;
		}
		for(x >>= 1; x; x >>= 1) {
			if(dc[x<<1] >= dc[x<<1|1]) {
				dc[x] = dc[x<<1];
				di[x] = di[x<<1];
			} else {
				dc[x] = dc[x<<1|1];
				di[x] = di[x<<1|1];
			}
		}
	}
	int get(int s, int e) {
		pii r(-INF, INF); int ri = -1;
		for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) {
				if(r < dc[s]) {
					r = dc[s];
					ri = di[s];
				}
				s++;
			}
			if(~e&1) {
				if(r < dc[e]) {
					r = dc[e];
					ri = di[e];
				}
				e--;
			}
		}
		return ri;
	}
} seg;

vector<int> AnsV;
int DC[MAXN], DI[MAXN];

int A[MAXN], B[MAXN];
int C[MAXM];

int N, M, Ans;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	{
		vector<pii> V;
		for(int i = 0, a, b; i < N; i++) {
			cin >> a >> b;
			V.eb(b, a);
		}
		sorv(V);
		for(int i = 1; i <= N; i++)
			tie(B[i], A[i]) = V[i-1];
	}
	for(int i = 1; i <= M; i++) cin >> C[i];
	sort(C+1, C+M+1);

	for(int i = 1, j, k; i <= N; i++) {
		if(C[M] < A[i]) continue;
		j = int(lower_bound(C+1, C+M+1, A[i]) - C);
		A[i] = C[j];
		k = seg.get(1, j);
		if(k < 1) {
			DC[i] = 1;
			DI[i] = -1;
		} else {
			DC[i] = DC[k] + 1;
			DI[i] = k;
		}
		seg.upd(j, DC[i], A[i], i);
	}

	{
		int idx = seg.get(1, M);
		if(idx < 1) {
			puts("0");
			return 0;
		}
		for(;;) {
			if(idx < 1) break;
			AnsV.eb(idx);
			idx = DI[idx];
		}
		revv(AnsV);
	}

	{
		int i = 1;
		for(int v : AnsV) {
			for(; i <= M && C[i] < A[v]; i++);
			if(M < i) break;
			Ans++;
			i++;
		}
	}

	cout << Ans << endl;
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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