2023/8/14题解

holycrap / 2023-08-15 / 原文

1. Codeforces Round 892 (Div. 2), problem: (D) Andrey and Escape from Capygrad

题目传送门
题意：在X轴上有n个传送门装置，每个传送门对应四个参数\(l\leq a\leq b\leq r\),可以在\([l,r]\)上任意一点传送到\([a,b]\)上任意一点。
有Q个询问，从某点出发最远到达哪个点。

思路：~~开始想的建树合并，但是复杂度太高。。~~实际上，从\(x_i\)点出发，最远走到的位置一定\(\geq x_i\) , 同时，\(b_i \leq r_i\)代表向左走对答案没有任何贡献，所以，策略是只向右移动。只要维护\([l_i,b_i]\)所构成的线段合并即可,即上图左黑端点右红端点的线段。
~~赛时最后一分钟想到但是没时间码了，可恶！~~

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<PII, int> PPI;
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define FOR(i,s,e)for(int i=(s);i<=(e);i++)
#define mem(a, b) memset((a), (b), sizeof(a))
#define inf 0x3f3f3f3f
#define seed 13331
#define MOD1 1000000007
#define MOD2 1000000009
#define MOD3 998244353
const int N = 2e5+7;
long long read(){
    char ch=getchar();long long nn=0,ssss=1;
    while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
    return nn*ssss;
}
void solve(int i_)
{
    int n;
    cin>>n;
    vector<array<int,2>> v,v2;
    for(int i=1;i<=n;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        v2.push_back({a,d});
    }
    sort(v2.begin(),v2.end());
    for(auto &[l,r]:v2)
    {
        if(!v.empty() && v.back()[1]>=l)
            v.back()[1] = max(v.back()[1],r);
        else
            v.push_back({l,r});
    }    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p;
        int j = lower_bound(v.begin(),v.end(),array{p+1,0})-1-v.begin();
	//p+1位置所在的线段无法到达，所求线段为左端点大于等于p+1的线段的上一条线段
        if(j>=0)
            p = max(p,v[j][1]);
        cout<<p<<" ";
    }
    cout<<"\n";
}
int main()
{
    io;
    int T=1,i_;
    cin>>T;
    for(i_=1;i_<=T;i_++)
    solve(i_);

    return 0;
}