Submission #1262235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262235		nguyenhuythach	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	1342 ms	161056 KiB

abduction2

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=5e4+1;
int n,m,q;
vector<int> a;
vector<int> b;
map<pair<pii,int>,int> mp;

void input()
{
    cin >> n >> m >> q;
    a.push_back(0);
    b.push_back(0);
    FOR(i,1,n)
    {
        int x; cin >> x;
        a.push_back(x);
    }
    FOR(i,1,m) 
    {
        int x; cin >> x;
        b.push_back(x);
    }
}

struct SEGTREE
{
    vector<int> tree;
    int n=0;
    
    void build(int id,int l,int r,vector<int> &a)
    {
        if(l==r)
        {
            tree[id]=a[l];
            return;
        }
        int mid=(l+r)/2;
        build(id*2,l,mid,a);
        build(id*2+1,mid+1,r,a);
        tree[id]=max(tree[id*2],tree[id*2+1]);
    }
    
    SEGTREE() = default;
    void init(int N,vector<int> &a)
    {
        n=N;
        tree.resize(4*n+5,0);
        build(1,1,n,a);
    }
    
    int getl(int id,int l,int r,int x,int val) //get in range [1,x]
    {
        if(x<l) return -1;
        if(tree[id]<=val) return -1;
        if(l==r) return l;
        int mid=(l+r)/2;
        int save=getl(id*2+1,mid+1,r,x,val);
        if(save>-1) return save;
        else return getl(id*2,l,mid,x,val);
    }
    
    int getr(int id,int l,int r,int x,int val) //get in range [x,n]
    {
        if(r<x) return 1e16;
        if(tree[id]<=val) return 1e16;
        if(l==r) return l;
        int mid=(l+r)/2;
        int save=getr(id*2,l,mid,x,val);
        if(save<1e16) return save;
        else return getr(id*2+1,mid+1,r,x,val);
    }
};

SEGTREE st1,st2;

int dfs(int x,int y,int d)
{
    if(x<=0 || y<=0 || x>n || y>m) return -1;
    if(mp.count({{x,y},d})) return mp[{{x,y},d}];
    if(d==1)
    {
        int l=0,r=m+1;
        if(y!=1) l=max(l,st2.getl(1,1,m,y-1,a[x]));
        if (y!=m) r=min(r,st2.getr(1,1,m,y+1,a[x]));
        return mp[{{x,y},d}]=max(y-l+dfs(x,l,2),r-y+dfs(x,r,2));
    }
    else
    {
        int l=0,r=n+1;
        if(x!=1) l=max(l,st1.getl(1,1,n,x-1,b[y]));
        if(x!=n) r=min(r,st1.getr(1,1,n,x+1,b[y]));
        return mp[{{x,y},d}]=max(x-l+dfs(l,y,1),r-x+dfs(r,y,1));
    }
}


void solve()
{
    st1.init(n,a);
    st2.init(m,b);
    while(q--)
    {
        int x,y; cin >> x >> y;
        cout << max(dfs(x,y,1),dfs(x,y,2)) << '\n';
    }
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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