Submission #233006

#	Time	Username	Problem	Language	Result	Execution time	Memory
233006		thebes	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	1899 ms	128644 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back
#define mt make_tuple

const int MN = 1e5+5;
int N, M, Q, i, j, x, y, dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
map<tuple<int,int,int>,ll> dp; vi a, b;

struct MaxSegmentTree{
    int st[2*MN], n;
    void build(int i,int s,int e,vi &vec){
        if(s!=e){
            build(2*i,s,(s+e)/2,vec);
            build(2*i+1,(s+e)/2+1,e,vec);
            st[i]=max(st[2*i],st[2*i+1]);
        }
        else st[i]=vec[s];
    }
    void init(vi vec){
        n = (int)vec.size();
        build(1,0,n-1,vec);
    }
    int lquery(int i,int s,int e,int ss,int se,int val){
        if(ss>se) return -1;
        if(s>=ss&&e<=se){
            if(st[i]<=val) return -1;
            else if(s==e) return e;
        }
        else if((s+e)/2<ss) return lquery(2*i+1,(s+e)/2+1,e,ss,se,val);
        else if((s+e)/2>=se) return lquery(2*i,s,(s+e)/2,ss,se,val);
        int r = lquery(2*i+1,(s+e)/2+1,e,ss,se,val);
        return r==-1?lquery(2*i,s,(s+e)/2,ss,se,val):r;
    }
    int lquery(int idx,int val){
        return lquery(1,0,n-1,0,idx-1,val);
    }
    int rquery(int i,int s,int e,int ss,int se,int val){
        if(ss>se) return -1;
        if(s>=ss&&e<=se){
            if(st[i]<=val) return -1;
            else if(s==e) return s;
        }
        else if((s+e)/2<ss) return rquery(2*i+1,(s+e)/2+1,e,ss,se,val);
        else if((s+e)/2>=se) return rquery(2*i,s,(s+e)/2,ss,se,val);
        int r = rquery(2*i,s,(s+e)/2,ss,se,val);
        return r==-1?rquery(2*i+1,(s+e)/2+1,e,ss,se,val):r;
    }
    int rquery(int idx,int val){
        return rquery(1,0,n-1,idx+1,n,val);
    }
}R,C;

ll solve(int x,int y,int d){
    if(dp.count(mt(x,y,d))) return dp[mt(x,y,d)];
    ll ans = 0;
    if(a[x]>b[y]){
        if(d!=0){
            int nxt = C.lquery(y,a[x]);
            if(~nxt) ans=max(ans,(ll)y-nxt+(ll)solve(x,nxt,1));
            else ans=max(ans,(ll)y);
        }
        if(d!=1){
            int nxt = C.rquery(y,a[x]);
            if(~nxt) ans=max(ans,(ll)nxt-y+(ll)solve(x,nxt,0));
            else ans=max(ans,(ll)M-1-y);
        }
    }
    else{
        if(d!=2){
            int nxt = R.lquery(x,b[y]);
            if(~nxt) ans=max(ans,(ll)x-nxt+(ll)solve(nxt,y,3));
            else ans=max(ans,(ll)x);
        }
        if(d!=3){
            int nxt = R.rquery(x,b[y]);
            if(~nxt) ans=max(ans,(ll)nxt-x+(ll)solve(nxt,y,2));
            else ans=max(ans,(ll)N-1-x);
        }
    }
    return dp[mt(x,y,d)]=ans;
}

int main(){
    scanf("%d%d%d",&N,&M,&Q);
    for(i=1;i<=N;i++){
        scanf("%d",&x);
        a.pb(x);
    }
    for(i=1;i<=M;i++){
        scanf("%d",&x);
        b.pb(x);
    }
    R.init(a), C.init(b);
    for(;Q;Q--){
        scanf("%d%d",&x,&y);
        ll sna = 0;
        for(i=0;i<4;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if(nx<1||nx>N||ny<1||ny>M) continue;
            sna=max(sna,(ll)solve(nx-1,ny-1,i)+1);
        }
        printf("%lld\n",sna);
    }
    return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&N,&M,&Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
abduction2.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
abduction2.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
abduction2.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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