52602023-04-24 12:52:39ZsofiaKeresztelyMágikus táblázatcpp14Time limit exceeded 0/100600ms15544 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<int> a, b;

bool ok(int mid){
    for (int i=1; i * i <= mid; i++){
        int di = (mid - 1) / i + 1;
        map<int, int> ma;
        int amax = -1e9, bmin = 1e9;
        if (i <= n && di <= m){
            for (int j=0; j<i; j++){
                ma[a[j]]++;
            }
            amax = max(amax, ma.begin()->first);
            for (int j=i; j<n; j++){
                ma[a[j]]++;
                ma[a[j-i]]--;
                if (!ma[a[j-i]]) ma.erase(a[j-i]);
                amax = max(amax, ma.begin()->first);
            }
            ma.clear();
            for (int j=0; j<di; j++){
                ma[b[j]]++;
            }
            bmin = min(bmin, ma.rbegin()->first);
            for (int j=di; j<m; j++){
                ma[b[j]]++;
                ma[b[j-i]]--;
                if (!ma[b[j-i]]) ma.erase(b[j-i]);
                bmin = min(bmin, ma.rbegin()->first);
            }
        }
        if (amax >= bmin) return true;
        amax = -1e9;
        bmin = 1e9;
        ma.clear();
        if (di <= n && i <= m){
            for (int j=0; j<di; j++){
                ma[a[j]]++;
            }
            amax = max(amax, ma.begin()->first);
            for (int j=di; j<n; j++){
                ma[a[j]]++;
                ma[a[j-i]]--;
                if (!ma[a[j-i]]) ma.erase(a[j-i]);
                amax = max(amax, ma.begin()->first);
            }
            ma.clear();
            for (int j=0; j<i; j++){
                ma[b[j]]++;
            }
            bmin = min(bmin, ma.rbegin()->first);
            for (int j=i; j<m; j++){
                ma[b[j]]++;
                ma[b[j-i]]--;
                if (!ma[b[j-i]]) ma.erase(b[j-i]);
                bmin = min(bmin, ma.rbegin()->first);
            }
        }
        if (amax >= bmin) return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    for (int &x : a){
        cin >> x;
    }
    for (int &x : b){
        cin >> x;
    }
    int l = 0, r = n * m + 1;
    while (l + 1 < r){
        int mid = (l + r) / 2;
        if (ok(mid)){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    cout << l;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1980 KiB
2Time limit exceeded600ms1896 KiB
subtask20/14
3Accepted13ms2404 KiB
4Wrong answer21ms2372 KiB
5Accepted3ms2496 KiB
6Wrong answer7ms2708 KiB
7Wrong answer4ms2716 KiB
8Accepted4ms2848 KiB
subtask30/27
9Time limit exceeded574ms2472 KiB
10Time limit exceeded575ms3388 KiB
11Time limit exceeded555ms2560 KiB
12Time limit exceeded563ms3620 KiB
13Time limit exceeded564ms2972 KiB
14Wrong answer211ms3800 KiB
15Time limit exceeded563ms4064 KiB
16Time limit exceeded564ms3540 KiB
17Time limit exceeded560ms4372 KiB
subtask40/21
18Time limit exceeded547ms4560 KiB
19Time limit exceeded573ms4232 KiB
20Time limit exceeded600ms4216 KiB
21Time limit exceeded552ms4280 KiB
22Wrong answer17ms5452 KiB
23Wrong answer17ms5456 KiB
24Time limit exceeded600ms4236 KiB
subtask50/38
25Time limit exceeded564ms9104 KiB
26Time limit exceeded561ms9112 KiB
27Time limit exceeded572ms9120 KiB
28Time limit exceeded564ms9092 KiB
29Time limit exceeded505ms9244 KiB
30Time limit exceeded569ms9200 KiB
31Time limit exceeded541ms9228 KiB
32Time limit exceeded558ms7432 KiB
33Time limit exceeded550ms7384 KiB
34Time limit exceeded577ms4596 KiB
35Time limit exceeded565ms6576 KiB
36Time limit exceeded600ms9628 KiB
37Time limit exceeded568ms5224 KiB
38Wrong answer398ms15544 KiB
39Time limit exceeded583ms9740 KiB
40Time limit exceeded558ms9652 KiB
41Time limit exceeded556ms9196 KiB
42Time limit exceeded560ms5068 KiB
43Time limit exceeded568ms7264 KiB
44Time limit exceeded568ms7376 KiB