Submission #1251938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251938		minhpk	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	1340 ms	159984 KiB

abduction2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,q;
int z[1000005];
int t[1000005];
int inf=1e16;
struct ST{
      int f[4000005]={0};

      void update(int id,int l,int r,int pos,int val){
           if (l==r){
              f[id]=val;
              return;
           }
           int mid=(l+r)/2;
           if (pos<=mid){
              update(id*2,l,mid,pos,val);
           }else{
              update(id*2+1,mid+1,r,pos,val);
           }
           f[id]=max(f[id*2],f[id*2+1]);
      }
      int getl(int id,int l,int r,int x,int y,int val){
          if (x>r || y<l){
              return -1;
          }
          if (f[id]<val){
            return -1;
          }
          if (l==r){
              return l;
          }
          int mid=(l+r)/2;
          int pre=getl(id*2+1,mid+1,r,x,y,val);
          if (pre>-1){
              return pre;
          }
          return getl(id*2,l,mid,x,y,val);
      }

      int getr(int id,int l,int r,int x,int y,int val){
           if (x>r || y<l){
              return inf;
           }
           if (f[id]<val){
               return inf;
           }
           if (l==r){
              return l;
           }
           int mid=(l+r)/2;

           int pre=getr(id*2,l,mid,x,y,val);
          if (pre<inf){
              return pre;
          }
          return getr(id*2+1,mid+1,r,x,y,val);
      }
};
ST f,f1;
map<pair<pair<int,int>,int>,int> m;
int solve(int x,int y,int d){
    if (x<=0 || y<=0 || x>a || y>b){
        return -1;
    }
    if (m.count({{x,y},d})){
        return m[{{x,y},d}];
    }
    if (d==1){
        int l=0;
        int r=b+1;
        if (y!=1){
            l=max(l,f1.getl(1,1,b,1,y-1,z[x]));
        }
        if (y!=b){
            r=min(r,f1.getr(1,1,b,y+1,b,z[x]));
        }
       return m[{{x,y},d}]=max(y-l+solve(x,l,2),r-y+solve(x,r,2));
    }else{
        int l=0;
        int r=a+1;
        if (x!=1){
            l=max(l,f.getl(1,1,a,1,x-1,t[y]));
        }
        if (x!=a){
            r=min(r,f.getr(1,1,a,x+1,a,t[y]));
        }
       return m[{{x,y},d}]=max(x-l+solve(l,y,1),r-x+solve(r,y,1));
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> q;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    for (int i=1;i<=b;i++){
         cin >> t[i];
    }
    for (int i=1;i<=a;i++){
         f.update(1,1,a,i,z[i]);
    }
    for (int i=1;i<=b;i++){
         f1.update(1,1,b,i,t[i]);
    }
    while (q--){
        int x,y;
        cin >> x >> y;
        int max1=max(solve(x,y,1),solve(x,y,2));
        cout << max1 << "\n";
    }

    return 0;
}

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