oj.uz

답안 #121049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121049 2019-06-26T04:00:38 Z 윤교준(#2970) Exhibition (JOI19_ho_t2) C++14
0 / 100
 11 ms 2432 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 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 d[MX*2];

	void init() {
		fill(d, d+MX*2, pii(-INF, INF));
	}
	void upd(int x, int c, int t) {
		pii r(c, -t);
		for(x += MX; x; x >>= 1)
			upmax(d[x], r);
	}
	pii get(int s, int e) {
		pii r(-INF, INF); for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) upmax(r, d[s++]);
			if(~e&1) upmax(r, d[e--]);
		}
		return r;
	}
} seg;

int DC[MAXN], DF[MAXN];

vector<int> VB;
int A[MAXN], B[MAXN];
int C[MAXM];

int N, M;

int getDF(int l, int v) {
	return int(lower_bound(C+l+1, C+M+1, v) - C);
}

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(a, b);
		}
		sorv(V);
		for(int i = 1; i <= N; i++)
			tie(A[i], B[i]) = V[i-1];
	}
	for(int i = 1; i <= M; i++) cin >> C[i];
	sort(C+1, C+M+1);

	for(int i = 1; i <= N; i++) VB.eb(B[i]);
	sorv(VB); univ(VB);

	for(int i = 1, j; i <= N; i++) {
		if(C[M] < A[i]) continue;
		j = int(lower_bound(allv(VB), B[i]) - VB.begin());
		pii ret = seg.get(0, j);
		if(ret.first < 1) {
			DC[i] = 1;
			DF[i] = getDF(0, A[i]);
		} else {
			DC[i] = ret.first + 1;
			DF[i] = getDF(-ret.second, A[i]);
		}
		if(DF[i] < M) seg.upd(j, DC[i], DF[i]);
	}

	cout << *max_element(DC+1, DC+N+1) << endl;
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 11 ms 2432 KB Output is correct
3 Correct 3 ms 2432 KB Output is correct
4 Correct 3 ms 2432 KB Output is correct
5 Incorrect 4 ms 2432 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 11 ms 2432 KB Output is correct
3 Correct 3 ms 2432 KB Output is correct
4 Correct 3 ms 2432 KB Output is correct
5 Incorrect 4 ms 2432 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 11 ms 2432 KB Output is correct
3 Correct 3 ms 2432 KB Output is correct
4 Correct 3 ms 2432 KB Output is correct
5 Incorrect 4 ms 2432 KB Output isn't correct
6 Halted 0 ms 0 KB -