Submission #1150679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150679		alir3za_zar3	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2591 ms	18124 KiB

Main

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    int n; cin >> n;
    int a[n+1] , b[n+1];
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=1; i<=n; i++)
        cin >> b[i];
    
    int q; cin >> q;
    while (q--)
    {
        int l,r; cin >> l >> r;
        set<pair<int,int>> A,B;
        for (int i=l; i<=r; i++)
        {
            A.insert( { a[i] , i } );
            B.insert( { b[i] , i } );
        }
        
        bool mrk = true;
        vector<pair<int,int>> op;
        while (!A.empty())
        {
            auto [x , idx] = *A.begin();
            auto [y , idy] = *B.begin();
            A.erase(A.begin());
            B.erase(B.begin());
            if (x < y)
            {
                mrk = false;
                break;
            }
            if (idx == idy)
            {
                if (B.empty())
                {
                    if (op.empty())
                    {
                        mrk = false;
                        break;
                    }
                    auto [v , u] = op.back();
                    if (v >= y)
                    {
                        op.push_back( { x , u } );
                        continue;
                    }
                    else
                    {
                        mrk = false;
                        break;
                    }
                }
                if (!op.empty())
                {
                    auto [v , u] = op.back();
                    if (v >= y)
                    {
                        op.push_back( { x , u } );
                        continue;
                    }
                }
                auto [z , idz] = *B.begin();
                if (x < z)
                {
                    mrk = false;
                    break;
                }
                B.erase(B.begin());
                B.insert({y,idy});
            }
            else
            {
                op.push_back({ x , y });
            }
        }
        if (mrk)
            cout << "Yes\n";
        else    
            cout << "No\n";
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12