Submission #1223751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223751		amine_aroua	Abduction 2 (JOI17_abduction2)	C++20	44 / 100	2501 ms	35340 KiB

abduction2

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

int h , w , q;
const int H = 5e4 + 5;
unordered_map<int , int> dp[2][H + 5];
int a[H + 5] , b[H + 5];
int sp[2][H+5][20];
int lg[H+5];
// 0 : --
// 1 : |
void build(int dir,int n){
    for(int i = 0; i < n; i++){
        sp[dir][i][0]= (dir==0 ? a[i] : b[i]);
    }
    for(int i=1 ; i < 18 ; i++){
        for(int j=0;j + (1<<i) <= n;j++){
            sp[dir][j][i]=max(sp[dir][j][i-1], sp[dir][j+(1<<(i-1))][i-1]);
        }
    }
}
int query(int dir,int l,int r){
    if(l > r)
        return -1;
    int d = lg[r-l+1];
    return max(sp[dir][l][d], sp[dir][r-(1<<d)+1][d]);
}
int dfs(int i , int j , int dir)
{
    if(dp[dir][i].find(j) != dp[dir][i].end())
    {
        return dp[dir][i][j];
    }
    if(dir == 0)
    {
        int val=a[i];
        int k = w;
        int lo = 0,hi = 0;
        if(j != w - 1)
        {
            lo = j , hi = w;
            while(lo + 1 < hi)
            {
                int md = (lo + hi)/2;
                if(query(1 , j+1 , md) <= val) lo = md;  
                else hi = md;
            }
            k = min(lo + 1 , w );
        }
        
        int k_ = -1;
        if(j != 0)
        {
            lo = -1 , hi = j;
            while(lo + 1 < hi)
            {
                int md = (lo + hi)/2;
                if(query(1 , md , j - 1) <= val)
                {
                    hi = md;
                }
                else
                    lo = md;
            }
            hi--;
            k_ = max(-1 , hi);
        }
        
        assert(k != j && k_ != j);
        if(b[k] > val)
        {
            dp[dir][i][j] = dfs(i , k , dir^1) + k - j;
        }
        else
        {
            dp[dir][i][j] = k - j;
        }
        if(k_ != -1 &&b[k_] > val){
            dp[dir][i][j]= max (dp[dir][i][j] , dfs(i,k_,dir^1) + j - k_);
        }
        else 
        {
            dp[dir][i][j]= max( dp[dir][i][j] , j - k_ );
        }
    }
    else
    {
        int val=b[j];
        int k = h;
        int lo = 0,hi = 0;
        if(i != h - 1)
        {
            lo = i , hi = h;
            while(lo + 1 < hi)
            {
                int md = (lo + hi)/2;
                if(query(0 , i + 1 , md) <= val)
                {
                    lo = md;
                }   
                else
                    hi = md;
            }
            k = min(lo + 1 , h);
        }
        int k_ = -1;
        if(i != 0)
        {
            lo = -1 , hi = i;
            while(lo + 1 < hi)
            {
                int md = (lo + hi)/2;
                if(query(0 , md , i - 1) <= val)
                {
                    hi = md;
                }
                else
                    lo = md;
            }
            hi--;
            k_ = max(-1 , hi);
        }
        if(a[k] > val)
        {
            dp[dir][i][j] = dfs(k , j , dir^1) + k - i;
        }
        else
        {
            dp[dir][i][j] = k - i;
        }
        if(k_ != -1&&a[k_] > val){
            dp[dir][i][j]= max (dp[dir][i][j] , dfs(k_,j,dir^1) + i - k_);
        }
        else
        {
            dp[dir][i][j] = max(dp[dir][i][j] , i - k_);
        }
    }
    return dp[dir][i][j];
}
//a[i=3] = 5: - - |b[j=3]=7 - - |b[j=8]=19 - - : 7 , 19  N 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>h>>w>>q;
    lg[1]=0;
    for(int i=2;i<H+4;i++){
        lg[i]=lg[i/2]+1;
    }
    for (int i=0; i<h; i++) {
        cin>>a[i];
    }
    for (int i=0; i<w; i++) {
        cin>>b[i];
    }
    build(0,h);
    build(1,w);
    while(q--){
        for(int dir = 0 ; dir < 2 ; dir++)
        {
            for(int i = 0 ; i <= H ;i++)
            {
                dp[dir][i].clear();
            }
        }
        int x,y;
        cin>>x>>y;
        x--;y--;
        cout << max(dfs(x,y,0),dfs(x,y,1))-1 <<'\n';
    }
}

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