Submission #1223719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223719		amine_aroua	Abduction 2 (JOI17_abduction2)	C++20	44 / 100	5092 ms	22580 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3" , "unroll-loops")
int h , w , q;
const int H = 5e4+1;
map<int , int> dp[2][H + 1];
int a[H + 1] , b[H + 1];
int sp[2][H+1][18];
int lg[H+1];
// 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 <= 17 ; 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 -1e9;
    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];
    }
    dp[dir][i][j]=0;
    if(dir == 0)
    {
        int val=a[i];
        int lo = j , hi = w;
        while(lo + 1 < hi)
        {
            int md = (lo + hi)>>1;
            if(query(1 , j+1 , md) <= val)
            {
                lo = md;
            }   
            else
                hi = md;
        }
        int k = min(lo + 1 , w -1);
        int K = j + 1;
        for(; K < w ; K++)
        {
            if(b[K] > val)
            {
                break;
            }
        }
        K = min(K , w - 1);
        assert(K == k);
        lo = 0 , hi = j+1 ;
        while(lo + 1 < hi)
        {
            int md = (lo + hi)>>1;
            if(query(1 , md - 1 , j - 1) <= val)
            {
                hi = md;
            }
            else
                lo = md;
        }
        hi--;
        int k_ = max(0 , hi - 1);
        if(b[k] > val)
        {
            dp[dir][i][j] = dfs(i , k , dir^1) + k - j;
        }
        else
        {
            dp[dir][i][j] = k - j;
        }
        if(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 lo = i , hi = h;
        while(lo + 1 < hi)
        {
            int md = (lo + hi)>>1;
            if(query(0 , i + 1 , md) <= val)
            {
                lo = md;
            }   
            else
                hi = md;
        }
        int k = min(lo + 1 , h - 1);
        lo = 0 , hi = i +1;
        while(lo + 1 < hi)
        {
            int md = (lo + hi)>>1;
            if(query(0 , md - 1 , i - 1) <= val)
            {
                hi = md;
            }
            else
                lo = md;
        }
        hi--;
        int k_ = max(0 , hi - 1);
        if(a[k] > val)
        {
            dp[dir][i][j] = dfs(k , j , dir^1) + k - i;
        }
        else
        {
            dp[dir][i][j] = k - i;
        }
        if(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];
}

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+1;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)) <<'\n';
    }
}

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