https://ac.nowcoder.com/acm/contest/54877/D
题目描述
猫猫从猫儿园回家，路过了一家宠物店。
这里有 nnn 只猫猫，每只猫猫有一个友善值，用正整数 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an 表示；每只猫猫有一个期望友善值，用正整数 c1,c2,...,cnc_1,c_2,...,c_nc1,c2,...,cn 表示。
有 mmm 个主人，每个主人有一个友善值，用正整数 b1,b2,...,bmb_1,b_2,...,b_mb1,b2,...,bm 表示；每个主人有一个期望友善值，用正整数 d1,d2,..,dmd_1,d_2,..,d_md1,d2,..,dm 表示。
猫猫喜欢友善的主人，主人也喜欢友善的猫猫。猫猫 xxx 可以被主人 yyy 领养，当且仅当 by≥cxb_y \geq c_xby≥cx 且 ax≥dya_x\geq d_yax≥dy，即双方都达到了对方的期望友善值。输入共五行。
对于猫猫 i=1,2,...,ni=1,2,...,ni=1,2,...,n，输出可能领养猫猫 iii 的主人中，最大的友善值。如果没有，输出 −1-1−1。
输入描述:
第一行两个整数 n,mn,mn,m，分别表示猫猫的数量和主人的数量。
第二行 nnn 个整数 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an 表示猫猫的友善值。
第三行 nnn 个整数 c1,c2,...,cnc_1,c_2,...,c_nc1,c2,...,cn 表示猫猫的期望友善值。
第四行 mmm 个整数 b1,b2,...,bmb_1,b_2,...,b_mb1,b2,...,bm 表示主人的友善值。
第五行 mmm 个整数 d1,d2,...,dmd_1,d_2,...,d_md1,d2,...,dm 表示主人的期望友善值。
1≤n,m≤2⋅105,1≤ai,bi,ci,di≤1091\leq n,m\leq 2\cdot 10^5,1\leq a_i,b_i,c_i,d_i\leq 10^{9}1≤n,m≤2⋅105,1≤ai,bi,ci,di≤109。
输出描述:
一行 nnn 个整数，第 iii 个整数表示可能领养猫猫 iii 的主人中，最大的友善值。如果没有，输出 −1-1−1。
示例1
输入
复制
2 110 101 100210
2 1
10 10
1 100
2
10
输出
复制
2 -1
2 -1
说明
两只猫猫都满足主人 1 的要求，但是主人不满足猫猫 2 的要求。
题解
#include <bits/stdc++.h>
using namespace std;
#define N 200010
int n, m;
int ans[N];
struct P {
int x, y, i;
} a[N], b[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i].x;
for (int i = 1; i <= n; ++i) cin >> a[i].y;
for (int i = 1; i <= n; ++i) a[i].i = i;
for (int i = 1; i <= m; ++i) cin >> b[i].x;
for (int i = 1; i <= m; ++i) cin >> b[i].y;
for (int i = 1; i <= m; ++i) b[i].i = i;
sort(a + 1, a + n + 1, [](P a, P b){return a.x < b.x;});
sort(b + 1, b + m + 1, [](P a, P b){return a.y < b.y;});
int mx = -1;
for (int i = 1, j = 0; i <= n; ++i) {
while (j < m && b[j + 1].y <= a[i].x)
++j, mx = max(mx, b[j].x);
// cout << j << '\n';
ans[a[i].i] = mx >= a[i].y ? mx : -1;
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
return 0;
}