Submission #1128007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128007		12345678	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1658 ms	91620 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, q, a[nx], b[nx], l[nx], r[nx], x[nx], y[nx], res[nx];
vector<int> qrs[nx], upd[nx];

struct mnsegtree
{
    int d[8*nx], lz[8*nx];
    void pushlz(int l, int r, int i)
    {
        if (lz[i]==-1) return;
        if (l!=r) lz[2*i]=lz[i], lz[2*i+1]=lz[i];
        d[i]=min(d[i], lz[i]);
        lz[i]=-1;
    }
    void build(int l, int r, int i, int vl)
    {
        d[i]=vl, lz[i]=-1;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i, vl);
        build(md+1, r, 2*i+1, vl);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1 ,r ,2*i+1, ql, qr, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return INT_MAX;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} mn;

struct mxsegtree
{
    int d[8*nx], lz[8*nx];
    void pushlz(int l, int r, int i)
    {
        if (lz[i]==-1) return;
        if (l!=r) lz[2*i]=lz[i], lz[2*i+1]=lz[i];
        d[i]=max(d[i], lz[i]);
        lz[i]=-1;
    }
    void build(int l, int r, int i, int vl)
    {
        d[i]=vl, lz[i]=-1;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i, vl);
        build(md+1, r, 2*i+1, vl);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1 ,r ,2*i+1, ql, qr, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} mx;

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        d[i]=n+1;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r ,2*i+1, idx, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return n+1;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return min(query(l, md ,2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) cin>>b[i];
    mn.build(1, 2*n, 1, n+1);
    for (int i=n; i>=1; i--)
    {
        y[i]=mn.query(1, 2*n, 1, b[i], a[i])-1;
        mn.update(1, 2*n, 1, b[i], a[i], i);
    }
    mx.build(1, 2*n+1, 1, 0);
    for (int i=1; i<=n; i++)
    {
        x[i]=mx.query(1, 2*n, 1, b[i], a[i])+1;
        mx.update(1, 2*n, 1, b[i], a[i], i);
    }
    for (int i=1; i<=n; i++) upd[y[i]].push_back(i);
    /*
    cout<<"x ";
    for (int i=1; i<=n; i++) cout<<x[i]<<' ';
    cout<<'\n';
    cout<<"y ";
    for (int i=1; i<=n; i++) cout<<y[i]<<' ';
    cout<<'\n';
    */
    s.build(1, n, 1);
    cin>>q;
    for (int i=1; i<=q; i++) cin>>l[i]>>r[i], qrs[r[i]].push_back(i);
    for (int i=n; i>=1; i--)
    {
        for (auto k:upd[i]) s.update(1, n, 1, k, x[k]);
        for (auto idx:qrs[i]) 
        {
            //cout<<"idx "<<idx<<'\n';
            if (s.query(1, n, 1, l[idx], r[idx])<=l[idx]) res[idx]=1;
        }
        /*
        cout<<"here "<<i<<':';
        for (int j=1; j<=n; j++) cout<<s.query(1, n, 1, j, j)<<' ';
        cout<<'\n';
        */
    }
    for (int i=1; i<=q; i++) cout<<((res[i])?"No\n":"Yes\n");
}

/*
l<x[i] and y[i]<r -> No
*/

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