Submission #318989

#	Time	Username	Problem	Language	Result	Execution time	Memory
318989		fivefourthreeone	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	1676 ms	142236 KiB

abduction2

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = atan(1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 50001;
map<array<int, 3>, ll> mp;
int H[mxN][2][20];
int W[mxN][2][20];
int h, w, q;
ll solve(int x, int y, int dir) {
    if(mp.find({x, y, dir})!=mp.end())return mp[{x, y, dir}];
    ll res = 0;
    if(dir==0) {
        int dxl = x-1;
        int dxr = x+1;
        int mx = W[y][0][0];
        uwu(lg, 20, 0) {
            //cout<<dxl<<" "<<dxr<<" x"<<endl;
            if(H[dxl][0][lg] <= mx) {
                dxl = max(0, dxl - (1<<lg));
            }
            if(H[dxr][1][lg] <= mx) {
                dxr = min(h+1, dxr + (1<<lg));
            }
        }
        //cout<<x<<" "<<y<<" "<<dir<<" "<<mx<<" "<<dxl<<" "<<dxr<<"\n";
        if(dxl == 0) res =  max(res, (ll)x - 1);
        else res = max(res, x - dxl + solve(dxl, y, 1));
        if(dxr == h+1) res = max(res, (ll)h - x);
        else res = max(res, dxr - x + solve(dxr, y, 1));
    }else {
        int dyl = y-1;
        int dyr = y+1;
        int mx = H[x][0][0];
        uwu(lg, 20, 0) {
            //cout<<dyl<<" "<<dyr<<" y"<<endl;
            if(W[dyl][0][lg] <= mx) {
                dyl = max(0, dyl - (1<<lg));
            }
            if(W[dyr][1][lg] <= mx) {
                dyr = min(w+1, dyr + (1<<lg));
            }
        }
        if(dyl == 0) res =  max(res, (ll)y - 1);
        else res = max(res, y - dyl + solve(x, dyl, 0));
        if(dyr == w+1) res = max(res, (ll)w - y);
        else res = max(res, dyr - y + solve(x, dyr, 0));
    }
    //cout<<x<<" "<<y<<" "<<dir<<" "<<res<<"\n";
    return mp[{x, y, dir}] = res;
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>h>>w>>q;
    owo(i, 1, h+1) {
        cin>>H[i][0][0];
        H[i][1][0] = H[i][0][0];
    }
    owo(i, 1, w+1) {
        cin>>W[i][0][0];
        W[i][1][0] = W[i][0][0];
    }
    owo(lg, 1, 20) {
        owo(dir, 0, 2) {
            int sn = (dir ? 1 : -1);
            owo(i, 1, h+1) {
                int nval = i + sn*(1<<(lg-1));
                nval = max(nval, 0);
                nval = min(nval, h+1);
                H[i][dir][lg] = max(H[i][dir][lg-1], H[nval][dir][lg-1]);
                //cout<<i<<" "<<dir<<" "<<lg<<" "<<H[i][dir][lg]<<" H\n";
            }
            owo(i, 1, w+1) {
                int nval = i + sn*(1<<(lg-1));
                nval = max(nval, 0);
                nval = min(nval, w+1);
                W[i][dir][lg] = max(W[i][dir][lg-1], W[nval][dir][lg-1]);
                //cout<<i<<" "<<dir<<" "<<lg<<" "<<W[i][dir][lg]<<" W\n";
            }
        }
    }
    int a, b;
    while(q--) {
        cin>>a>>b;
        cout<<(max(solve(a, b, 0), solve(a, b, 1)))<<"\n";
        //ayaya;
    }
    return 0;
}

Compilation message (stderr)

abduction2.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
abduction2.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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