Submission #1077393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077393		urd05	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	474 ms	11300 KiB

abduction2

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

int n,m,q;
int a[50005];
int b[50005];
typedef pair<int,int> P;
map<P,int> mp;
int as0=0;
int as1=0;
int bs0=0;
int bs1=0;
P va0[50005];
P va1[50005];
P vb0[50005];
P vb1[50005];
vector<P> press;
long long dp[500005];
int sa0[50001];
int sa1[50001];
int sb0[50005];
int sb1[50005];
int cx,cy;

long long ans(long long x,long long y,int d=-1) {
    int ind;
    if (a[x]<b[y]) {
        if (y>=cy) {
            ind=2*x+1;
        }
        else {
            ind=2*x;
        }
    }
    else {
        if (x>=cx) {
            ind=2*(n+5+y)+1;
        }
        else {
            ind=2*(n+5+y);
        }
    }
    if (dp[ind]!=-1) {
        return dp[ind];
    }
    bool flag;
    if (a[x]>b[y]) {
        flag=false;
    }
    else {
        flag=true;
    }
    long long ret=0;
    if (!flag) {
        if (d!=1) {
            int i0=sb0[x];
            if (i0==bs0) {
                ret=max(ret,y-1);
            }
            else {
                ret=max(ret,y-vb0[i0].second+ans(x,vb0[i0].second));
            }
        }
        if (d!=3) {
            int i1=sb1[x];
            if (i1==bs1) {
                ret=max(ret,m-y);
            }
            else {
                ret=max(ret,vb1[i1].second-y+ans(x,vb1[i1].second));
            }
        }
    }
    else {
        if (d!=0) {
            int i0=sa0[y];
            if (i0==as0) {
                ret=max(ret,x-1);
            }
            else {
                ret=max(ret,x-va0[i0].second+ans(va0[i0].second,y));
            }
        }
        if (d!=2) {
            int i1=sa1[y];
            if (i1==as1) {
                ret=max(ret,n-x);
            }
            else {
                ret=max(ret,va1[i1].second-x+ans(va1[i1].second,y));
            }
        }
    }
    //printf(".%d %d %d\n",x,y,ret);
    return dp[ind]=ret;
}

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<P> av;
vector<P> bv;

int main(void) {
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        av.push_back(P(a[i],i));
    }
    for(int i=1;i<=m;i++) {
        scanf("%d",&b[i]);
        bv.push_back(P(b[i],i));
    }
    sort(av.begin(),av.end());
    sort(bv.begin(),bv.end());
    for(int ind=0;ind<q;ind++) {
        int x,y;
        scanf("%d %d",&x,&y);
        bool f=false;
        if (a[x]>b[y]) {
            f=true;
        }
        bool ff=false;
        long long ret=0;
        for(int j=0;j<4;j++) {
            int nx=x+dx[j];
            int ny=y+dy[j];
            if (nx<=0||nx>n||ny<=0||ny>m) {
                continue;
            }
            bool nf=false;
            if ((f&&(j&1))||(!f&&(j==0||j==2))) {
                if (ff) {
                    continue;
                }
                nf=true;
                ff=true;
            }
            if (nf) {
                nx=x;
                ny=y;
            }
            cx=nx;
            cy=ny;
            int pr=-1;
            as0=0;
            as1=0;
            bs0=0;
            bs1=0;
            for(int i=nx;i<=n;i++) {
                if (a[i]>pr) {
                    va1[as1++]=(P(a[i],i));
                    pr=a[i];
                }
            }
            pr=-1;
            for(int i=nx;i>0;i--) {
                if (a[i]>pr) {
                    va0[as0++]=(P(a[i],i));
                    pr=a[i];
                }
            }
            pr=-1;
            for(int i=ny;i<=m;i++) {
                if (b[i]>pr) {
                    vb1[bs1++]=(P(b[i],i));
                    pr=b[i];
                }
            }
            pr=-1;
            for(int i=ny;i>0;i--) {
                if (b[i]>pr) {
                    vb0[bs0++]=(P(b[i],i));
                    pr=b[i];
                }
            }
            int i0=0;
            int i1=0;
            //sort(press.begin(),press.end());
            //press.erase(unique(press.begin(),press.end()),press.end());
            memset(dp,-1,sizeof(dp));
            i0=0;
            i1=0;
            for(int i=0;i<n;i++) {
                while (i0<bs0&&vb0[i0].first<av[i].first) {
                    i0++;
                }
                while (i1<bs1&&vb1[i1].first<av[i].first) {
                    i1++;
                }
                sb0[av[i].second]=i0;
                sb1[av[i].second]=i1;
            }
            i0=0;
            i1=0;
            for(int i=0;i<m;i++) {
                while (i0<as0&&va0[i0].first<bv[i].first) {
                    i0++;
                }
                while (i1<as1&&va1[i1].first<bv[i].first) {
                    i1++;
                }
                sa0[bv[i].second]=i0;
                sa1[bv[i].second]=i1;
            }
            if (!nf)
            ret=max(ret,ans(nx,ny,j)+1);
            else {
                ret=max(ret,ans(x,y,-1));
            }
            //printf(".\n");
        }
        printf("%lld\n",ret);
    }
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
abduction2.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~
abduction2.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56