90pts求助,第一个点RE
查看原帖
90pts求助,第一个点RE
995853
lwxxs楼主2024/7/11 15:32
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int,int> mk;
typedef long long ll;
const int N=5e6+10;
int a[N];
int n,m;
vector<int>res;
vector<int>year;
int find(int x)
{
    return lower_bound(res.begin(),res.end(),x)-res.begin();
}
int maxv=0;
struct node
{
    int l,r;
    ll maxv;
}tr[N*4];
void pushup(int u)
{
    tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
}
void build(int u,int l,int r)
{   tr[u]={l,r};
    if(l==r)
    {
        tr[u].maxv=mk[res[l]];
        return;
    }
    else{
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        return tr[u].maxv;
    }
    else {
        int mid=tr[u].l+tr[u].r>>1;
        ll mas=0;
        if(l<=mid)mas=max(mas,query(u<<1,l,r));
        if(r>mid)mas=max(mas,query(u<<1|1,l,r));
        return mas;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int y,r;
        cin>>y>>r;
        year.push_back(y);
        maxv=max(y,maxv);
        mk[y]=r;
        res.push_back(y);
    }
    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    build(1,0,res.size()-1);
    cin>>m;
    while(m--)
    {   int flag=0;
        int y1,x1;
        cin>>y1>>x1;
        int case1=year[lower_bound(year.begin(),year.end(),y1)-year.begin()]==y1?1:0;
        int case2=year[lower_bound(year.begin(),year.end(),x1)-year.begin()]==x1?1:0;
        int y=find(y1);
        int x=find(x1);
        int case3=x1-y1==x-y?1:0;
        if(!case1)y--;
        //if(y<0)y=0;
        // if(!case1)
        // {
        //     y--;
        //     if(y<0)y=0;
        // }
        if(case1&&case2&&case3&&query(1,y,y)>=query(1,x,x)&&query(1,y+1,x-1)<query(1,x,x))
        {
            cout<<"true"<<endl;
        }
        else if((case2&&query(1,y+1,x-1)>=query(1,x,x))||(case1&&query(1,y+1,x-1)>=query(1,y,y))||(case1&&case2&&query(1,x,x)>query(1,y,y)))
        {
            cout<<"false"<<endl;
        }
        else{
            cout<<"maybe"<<endl;
        }
    }
    return 0;
}

2024/7/11 15:32
加载中...