제출 #1346855

#제출 시각아이디문제언어결과실행 시간메모리
1346855alexddCard Collection (JOI24_collection)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 200005;
const int MAXQ = 200005;

const int INF = 2e9;

int n,q;
int a[MAXN], b[MAXN];
int setx[MAXQ], sety[MAXQ];
bool rez[MAXQ];

void solve_separate()//we will get (setx, sety) from 2 separate elements
{
    for(int i=1;i<=q;i++)
    {
        int maxri = -INF, maxle = -INF;
        for(int j=1;j<=n;j++)
        {
            if(a[j] <= setx[i])
            {
                maxri = max(maxri, b[j]);
            }
            if(b[j] <= sety[i])
            {
                maxle = max(maxle, a[j]);
            }
        }
        if(!(maxle >= setx[i] && maxri >= sety[i]))
            continue;

        int cnt_both = 0, cnt_x = 0, cnt_y = 0;
        for(int j=1;j<=n;j++)
        {
            if(a[j] == setx[i] && b[j] == sety[i])
                cnt_both++;
            else if(a[j] == setx[i])
                cnt_x++;
            else if(b[j] == sety[i])
                cnt_y++;
        }

        if(!((cnt_x > 0 && cnt_y + cnt_both > 0) || (cnt_y > 0 && cnt_x + cnt_both > 0)))
            continue;

        rez[i] = 1;
    }
}

void solve_one()//we will get (setx, sety) from the same element
{
    for(int i=1;i<=q;i++)
    {
        int cnt_both = 0;
        for(int j=1;j<=n;j++)
        {
            if(a[j] == setx[i] && b[j] == sety[i])
                cnt_both++;
        }

        if(cnt_both == 0)
            continue;

        bool found = 0;
        if(cnt_both > 1)
            found = 1;
        for(int j=1;j<=n;j++)
        {
            if(a[j] >= setx[i] && b[j] >= sety[i] && !(a[j] == setx[i] && b[j] == sety[i]))
            {
                found = 1;
            }
        }

        if(!found)
            continue;

        rez[i] = 1;
    }
}

void flip()
{
    for(int i=1;i<=n;i++)
    {
        a[i] = -a[i];
        b[i] = -b[i];
    }
    for(int i=1;i<=q;i++)
    {
        setx[i] = -setx[i];
        sety[i] = -sety[i];
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=q;i++)
    {
        cin>>setx[i]>>sety[i];
    }

    solve_separate();
    solve_one();

    flip();
    solve_separate();
    solve_one();
    flip();

    for(int i=1;i<=q;i++)
        if(rez[i])
            cout<<i<<" ";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...