【离线】牛客小白月赛71 D-猫猫与主人

蔚落 2024-03-22 09:04 59阅读 0赞

**还是不懂离线算法，感觉不是很会啊**

[D-猫猫与主人\_牛客小白月赛71(重现赛) (nowcoder.com)][D-_71_ _nowcoder.com]

题意：

![06b7b6c30f2240dc94073eaf73bd5fa3.png][]

思路：

把猫猫和主人的属性想成二维坐标

![5b0c272b97924cbb93f6f1c0bca90506.jpeg][]

这样，对于每一个主人，答案就是他的左上方那几个点的y坐标的最大值

但是，如果询问的顺序不是按x轴从小到大的，那么就不能维护，如果是，那么只需要在从左到右遍历的过程中就能维护了（DS思想）

所以只需要将询问离线，然后从左到右遍历即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    struct ty{
    	int x,y,id;
    }c[mxn],q[mxn];
    
    int n,m,x;
    int ans[mxn];
    
    bool cmp(ty a,ty b){
    	if(a.x!=b.x) return a.x<b.x;
    	if(a.y!=b.y) return a.y<b.y;
    	return a.id<b.id;
    } 
    void solve(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) c[i].id=i;
    	for(int i=1;i<=n;i++) cin>>c[i].x;
    	for(int i=1;i<=n;i++) cin>>c[i].y;
    	for(int i=1;i<=m;i++) cin>>q[i].y;
    	for(int i=1;i<=m;i++) cin>>q[i].x;
    	sort(c+1,c+1+n,cmp);
    	sort(q+1,q+1+m,cmp);
    	int idx=1,mx=-1;
    	for(int i=1;i<=n;i++){
    		while(idx<=m&&q[idx].x<=c[i].x){
    			mx=max(mx,q[idx].y);
    			idx++;
    		}
    		if(mx>=c[i].y) ans[c[i].id]=mx;
    		else ans[c[i].id]=-1;
    	}
    	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[D-_71_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/56661/D
[06b7b6c30f2240dc94073eaf73bd5fa3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/08678b6be8464547b958205e03b6aa3e.png
[5b0c272b97924cbb93f6f1c0bca90506.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/102b68dd35b04ed6b89817324fdfd381.png