oj.uz

Submission #1080209

# Submission time Handle Problem Language Result Execution time Memory
1080209 2024-08-29T08:00:48 Z Evirir Abduction 2 (JOI17_abduction2) C++17
13 / 100
 354 ms 524288 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;

constexpr ii del[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int n,m,Q;
vector<int> a, b, dp;
vector<vector<int>> adj;
vector<bool> vst;

void read()
{
    cin>>n>>m>>Q;
    a.resize(n); b.resize(m);
    forn(i,0,n) cin>>a[i];
    forn(i,0,m) cin>>b[i];
    vector<int> v(all(a));
    for (const auto x : b) v.pb(x);
    sort(all(v));
    unordered_map<int, int> mp;
    forn(i,0,sz(v)) mp[v[i]] = i;
    for (auto& x : a) x = mp[x];
    for (auto& x : b) x = mp[x];
}

int getid(int x, int y, int d)
{
    return (x * m + y) * 4 + d;
}

array<int, 3> unid(int id)
{
    int d = id % 4;
    id /= 4;
    int y = id % m;
    int x = id /= m;
    return {x, y, d};
}

bool oob(int x, int y)
{
    return min(x, y) < 0 || x >= n || y >= m;
}

void dfs(int u)
{
    if (vst[u]) return;
    vst[u] = 1;
    for (const auto v : adj[u])
    {
        if (!vst[v]) dfs(v);
        dp[u] = max(dp[u], dp[v] + 1);
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    read();
    int ncnt = n * m * 4;
    adj.resize(ncnt);
    forn(i,0,n) forn(j,0,m)
    {
        forn(d,0,4)
        {
            auto [dx, dy] = del[d];
            int x1 = i + dx, y1 = j + dy;
            if (oob(x1, y1)) continue;
            int id = getid(i, j, d);
            bool chg;
            if (d <= 1) chg = b[j] < a[x1];
            else chg = a[i] < b[y1];
            if (!chg)
            {
                int id1 = getid(x1, y1, d);
                adj[id].pb(id1);
            }
            else
            {
                int id1s[]{getid(x1, y1, d ^ 2), getid(x1, y1, d ^ 3)};
                for (auto v : id1s) adj[id].pb(v);
            }
        }
    }

    dp.resize(ncnt);
    vst.resize(ncnt);
    forn(i,0,n) forn(j,0,m) forn(d,0,4)
    {
        int id = getid(i, j, d);
        if (vst[id]) continue;
        dfs(id);
    }

    forn(z,0,Q)
    {
        int x,y; cin>>x>>y; x--; y--;
        int ans = 0;
        forn(d,0,4)
        {
            int id = getid(x, y, d);
            ans = max(ans, dp[id]);
        }
        cout << ans << '\n';
    }

    // cout<<"dp:\n";
    // forn(i,0,n) forn(j,0,m) forn(d,0,4)
    // {
    //     int id = getid(i, j, d);
    //     cout << "(" << i << "," << j << "," << d << ") -> " << dp[id] << '\n';
    // }
    // cout<<'\n';
    // cout<<"adj:\n";
    // forn(i,0,n) forn(j,0,m) forn(d,0,4)
    // {
    //     int id = getid(i, j, d);
    //     cout << "(" << i << "," << j << "," << d << ") ->";
    //     for (const auto v : adj[id])
    //     {
    //         auto [i1, j1, d1] = unid(v);
    //         cout<<' '<<" (" << i1 << ',' << j1 << ',' << d1 << ")";
    //     }
    //     cout<<'\n';
    // }

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Runtime error 354 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Runtime error 354 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Runtime error 354 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -