Submission #363671

#	Time	Username	Problem	Language	Result	Execution time	Memory
363671		denkendoemeer	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	2130 ms	128364 KiB

abduction2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=1e9;
struct ain
{
    int aint[(1<<18)];
    void update(int nod,int st,int dr,int poz,int val)
    {
        if (st==dr){
            aint[nod]=val;
            return ;
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
            update(nod*2,st,mij,poz,val);
        else
            update(nod*2+1,mij+1,dr,poz,val);
        aint[nod]=max(aint[nod*2],aint[nod*2+1]);
    }
    int query1(int nod,int st,int dr,int poz,int val)
    {
        if (poz<=st || aint[nod]<val)
            return inf;
        if (st==dr)
            return st;
        int mij=(st+dr)/2,ans;
        ans=query1(nod*2+1,mij+1,dr,poz,val);
        if (ans<poz)
            return ans;
        return query1(nod*2,st,mij,poz,val);
    }
    int query2(int nod,int st,int dr,int poz,int val)
    {
        if (dr<=poz || aint[nod]<val)
            return -1;
        if (st==dr)
            return st;
        int mij=(st+dr)/2,ans;
        ans=query2(nod*2,st,mij,poz,val);
        if (ans>poz)
            return ans;
        return query2(nod*2+1,mij+1,dr,poz,val);
    }
}ai1,ai2;
ll quer1(int x,int y);
ll quer2(int x,int y);
int h,w,a[50005],b[50005];
ll has(int x,int y)
{
    return 1LL*x*50003+y;
}
map<ll,ll>mp1,mp2;
ll quer1(int x,int y)
{
    if (mp1[has(x,y)])
        return mp1[has(x,y)];
    ll ans1,ans2;
    int poz;
    poz=ai1.query1(1,1,h,x,b[y]);
    if (poz<x)
        ans1=quer2(poz,y)+x-poz;
    else
        ans1=x-1;
    poz=ai1.query2(1,1,h,x,b[y]);
    if (poz>x)
        ans2=quer2(poz,y)+poz-x;
    else
        ans2=h-x;
    mp1[has(x,y)]=max(ans1,ans2);
    return max(ans1,ans2);
}
ll quer2(int x,int y)
{
    if (mp2[has(x,y)])
        return mp2[has(x,y)];
    ll ans1,ans2;
    int poz;
    poz=ai2.query1(1,1,w,y,a[x]);
    if (poz<y)
        ans1=quer1(x,poz)+y-poz;
    else
        ans1=y-1;
    poz=ai2.query2(1,1,w,y,a[x]);
    if (poz>y)
        ans2=quer1(x,poz)+poz-y;
    else
        ans2=w-y;
    mp2[has(x,y)]=max(ans1,ans2);
    ll aux=mp2[has(x,y)];
    return aux;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int q,i;
    scanf("%d%d%d",&h,&w,&q);
    for(i=1;i<=h;i++)
        scanf("%d",&a[i]),ai1.update(1,1,h,i,a[i]);
    for(i=1;i<=w;i++)
        scanf("%d",&b[i]),ai2.update(1,1,w,i,b[i]);
    for(i=1;i<=q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        ll a=quer1(x,y);
        ll b=quer2(x,y);
        printf("%lld\n",max(a,b));
    }
return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d%d%d",&h,&w,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
abduction2.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |         scanf("%d",&a[i]),ai1.update(1,1,h,i,a[i]);
      |         ~~~~~^~~~~~~~~~~~
abduction2.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |         scanf("%d",&b[i]),ai2.update(1,1,w,i,b[i]);
      |         ~~~~~^~~~~~~~~~~~
abduction2.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         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