oj.uz

Submission #1080626

# Submission time Handle Problem Language Result Execution time Memory
1080626 2024-08-29T11:41:52 Z kwongweng Abduction 2 (JOI17_abduction2) C++17
23 / 100
 267 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];
        if (a[s] < b[t]){
            ans = max(ans, t);
            ROF(j,t-1,0){
                if (b[j] > a[s]){
                    ans = max(ans,dist[s][j] + t-j); break;
                }
            }
            ans = max(ans, m-1-t);
            FOR(j,t+1,m){
                if (b[j]>a[s]){
                    ans = max(ans,dist[s][j] + j-t); break;
                }
            }
        }else{
            ans = max(ans, s);
            ROF(j,s-1,0){
                if (a[j] > b[t]){
                    ans = max(ans,dist[j][t] + s-j); break;
                }
            }
            ans = max(ans, n-1-s);
            FOR(j,s+1,n){
                if (a[j] > b[t]){
                    ans = max(ans, dist[j][t] + j-s); break;
                }
            }
        }
        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 0 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 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 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 0 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 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 50 ms 31836 KB Output is correct
13 Correct 51 ms 31860 KB Output is correct
14 Correct 61 ms 31860 KB Output is correct
15 Correct 57 ms 31832 KB Output is correct
16 Correct 55 ms 31776 KB Output is correct
17 Correct 38 ms 31776 KB Output is correct
18 Correct 37 ms 31836 KB Output is correct
19 Correct 40 ms 31836 KB Output is correct
20 Correct 38 ms 30672 KB Output is correct
21 Correct 37 ms 31064 KB Output is correct
22 Correct 38 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 0 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 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 50 ms 31836 KB Output is correct
13 Correct 51 ms 31860 KB Output is correct
14 Correct 61 ms 31860 KB Output is correct
15 Correct 57 ms 31832 KB Output is correct
16 Correct 55 ms 31776 KB Output is correct
17 Correct 38 ms 31776 KB Output is correct
18 Correct 37 ms 31836 KB Output is correct
19 Correct 40 ms 31836 KB Output is correct
20 Correct 38 ms 30672 KB Output is correct
21 Correct 37 ms 31064 KB Output is correct
22 Correct 38 ms 31836 KB Output is correct
23 Runtime error 267 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 31836 KB Output isn't correct
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 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 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 50 ms 31836 KB Output is correct
13 Correct 51 ms 31860 KB Output is correct
14 Correct 61 ms 31860 KB Output is correct
15 Correct 57 ms 31832 KB Output is correct
16 Correct 55 ms 31776 KB Output is correct
17 Correct 38 ms 31776 KB Output is correct
18 Correct 37 ms 31836 KB Output is correct
19 Correct 40 ms 31836 KB Output is correct
20 Correct 38 ms 30672 KB Output is correct
21 Correct 37 ms 31064 KB Output is correct
22 Correct 38 ms 31836 KB Output is correct
23 Runtime error 267 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -