oj.uz

Submission #1080641

# Submission time Handle Problem Language Result Execution time Memory
1080641 2024-08-29T11:48:46 Z kwongweng Abduction 2 (JOI17_abduction2) C++17
27 / 100
 280 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long double ld;
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=a; i>=b; i--)
#define pb push_back
#define fi first
#define se second
#define ms memset
typedef complex<ld> pt;


int main(){
    ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    int n,m,q; cin>>n>>m>>q;
    vi a(n), b(m); vii p;
    FOR(i,0,n){
        cin>>a[i]; p.pb({a[i],i});
    }
    FOR(i,0,m){
        cin>>b[i]; p.pb({b[i],i+n});
    }
    sort(p.rbegin(), p.rend());
    ll dist[n][m]; ms(dist,0,sizeof(dist));
    vi useda(n), usedb(m);
    FOR(i,0,n+m){
        if (p[i].se >= n){
            int id = p[i].se - n;
            int cur = 0;
            FOR(j,0,n){
                if (useda[j]){
                    cur = j; continue;
                }
                ll d = 0;
                if (cur > 0 || useda[0]) d = dist[cur][id]; 
                dist[j][id] = d + (j-cur);
            }
            cur = n-1;
            ROF(j,n-1,0){
                if (useda[j]){
                    cur = j; continue;
                }
                ll d = 0;
                if (cur<n-1 || useda[n-1]) d = dist[cur][id];
                dist[j][id] = max(dist[j][id], d + (cur-j));
            }
            usedb[id] = 1; continue;
        }
        int id = p[i].se, cur = 0;
        FOR(j,0,m){
            if (usedb[j]){
                cur = j; continue;
            }
            ll d = 0; if (cur>0 || usedb[0]) d = dist[id][cur];
            dist[id][j] = d + (j-cur);
        }
        cur = m-1;
        ROF(j,m-1,0){
            if (usedb[j]){
                cur = j; continue;
            }
            ll d = 0; if (cur<m-1 || usedb[m-1]) d = dist[id][cur];
            dist[id][j] = max(dist[id][j], d + (cur-j));
        }
        useda[id] = 1;
    }
    FOR(i,0,q){
        ll s,t; cin>>s>>t;
        s--; t--;
        ll ans = dist[s][t];
        bool sol = true;
        if (a[s] < b[t]){
            ROF(j,t-1,0){
                if (b[j] > a[s]){
                    ans = max(ans,dist[s][j] + t-j); sol = false; break;
                }
            }
            if (sol) ans = max(ans, t);
            sol = true;
            FOR(j,t+1,m){
                if (b[j]>a[s]){
                    ans = max(ans,dist[s][j] + j-t); sol = false; break;
                }
            }
            if (sol) ans = max(ans, m-1-t);
        }else{
            bool sol = true;
            ROF(j,s-1,0){
                if (a[j] > b[t]){
                    ans = max(ans,dist[j][t] + s-j); sol=false; break;
                }
            }
            if (sol) ans=max(ans,s);
            sol = true;
            FOR(j,s+1,n){
                if (a[j] > b[t]){
                    ans = max(ans, dist[j][t] + j-s); sol=false; break;
                }
            }
            if (sol) ans = max(ans, n-1-s);
        }
        cout<<ans<<"\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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
10.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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 78 ms 31568 KB Output is correct
13 Correct 48 ms 31832 KB Output is correct
14 Correct 57 ms 31836 KB Output is correct
15 Correct 54 ms 31836 KB Output is correct
16 Correct 52 ms 31832 KB Output is correct
17 Correct 35 ms 31832 KB Output is correct
18 Correct 39 ms 31836 KB Output is correct
19 Correct 40 ms 31836 KB Output is correct
20 Correct 36 ms 30808 KB Output is correct
21 Correct 38 ms 31064 KB Output is correct
22 Correct 35 ms 31836 KB Output is correct

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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 78 ms 31568 KB Output is correct
13 Correct 48 ms 31832 KB Output is correct
14 Correct 57 ms 31836 KB Output is correct
15 Correct 54 ms 31836 KB Output is correct
16 Correct 52 ms 31832 KB Output is correct
17 Correct 35 ms 31832 KB Output is correct
18 Correct 39 ms 31836 KB Output is correct
19 Correct 40 ms 31836 KB Output is correct
20 Correct 36 ms 30808 KB Output is correct
21 Correct 38 ms 31064 KB Output is correct
22 Correct 35 ms 31836 KB Output is correct
23 Runtime error 280 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 31832 KB Output is correct
2 Correct 55 ms 31836 KB Output is correct
3 Correct 51 ms 31824 KB Output is correct
4 Correct 53 ms 31832 KB Output is correct
5 Correct 57 ms 31832 KB Output is correct
6 Correct 37 ms 31836 KB Output is correct
7 Correct 46 ms 31836 KB Output is correct
8 Correct 36 ms 32088 KB Output is correct
9 Correct 37 ms 31280 KB Output is correct
10 Correct 36 ms 31580 KB Output is correct
11 Correct 41 ms 31832 KB Output is correct

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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 78 ms 31568 KB Output is correct
13 Correct 48 ms 31832 KB Output is correct
14 Correct 57 ms 31836 KB Output is correct
15 Correct 54 ms 31836 KB Output is correct
16 Correct 52 ms 31832 KB Output is correct
17 Correct 35 ms 31832 KB Output is correct
18 Correct 39 ms 31836 KB Output is correct
19 Correct 40 ms 31836 KB Output is correct
20 Correct 36 ms 30808 KB Output is correct
21 Correct 38 ms 31064 KB Output is correct
22 Correct 35 ms 31836 KB Output is correct
23 Runtime error 280 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -