31522023-02-20 19:08:59Szin AttilaMágikus táblázatcpp14Time limit exceeded 62/100602ms119612 KiB
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const ll maxN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e12 + 7;

struct Node{
    ll val, ind;
    ll l, r;
    Node(ll x, ll ind){
        val = x;
        this->ind = ind;
    }
    Node() {
        val = -1;
        ind = -1;
    }
};

struct LazyTree{
    vector<Node> t;
    vector<ll> lazy;
    ll maxn;

    void build(ll v, ll l, ll r) {
        if(v > 4*maxn) return;
        t[v].l = l;
        t[v].r = r;

        ll mid = (l+r)/2;

        build(v*2, l, mid);
        build(v*2+1, mid+1, r);
    }

    LazyTree(ll n) : maxn(n) {
        for(ll i = 0; i <= 4*maxn; i++) {
            t.push_back(Node(0, i));
        }
        lazy.resize(4*n+1, 0);
        build(1, 1, n);
    }

    void push(ll ind) {
        t[ind*2].val += lazy[ind];
        lazy[ind*2] += lazy[ind];
        t[ind*2+1].val += lazy[ind];
        lazy[ind*2+1] += lazy[ind];
        lazy[ind] = 0;
    }

    ll merge(ll a, ll b) {
        return max(a,b);
    }

    void updateNode(ll ind) {
        push(ind);
        t[ind].val = merge(t[ind*2].val, t[ind*2+1].val);   
    }

    void update(ll v, ll ql, ll qr, ll added) {
        ll vl = t[v].l, vr = t[v].r;
        
        if(ql > qr) return;
        if(vl == ql && vr == qr) {
            lazy[v] += added;
            t[v].val += added;
        }
        else {
            push(v);
            ll mid = (vl + vr) / 2;
            update(v*2, ql, min(qr, mid), added);
            update(v*2+1, max(mid+1, ql), qr, added);
            updateNode(v);
        }
    }

    ll query(ll v, ll ql, ll qr) {
        if(ql < 1) return 0;
        ll vl = t[v].l, vr = t[v].r;
        if(ql > qr) return 0;
        if(vl >= ql && vr <= qr) return t[v].val;
        push(v);
        ll mid = (vl + vr) / 2;

        return merge(query(v*2, ql, min(mid, qr)),
                query(v*2+1, max(mid+1, ql), qr));
    }
};

vector<ll> kozos;

ll get_pos(ll k){
  return (ll)(lower_bound(kozos.begin(),kozos.end(), k) - kozos.begin());
}

int main() {

#ifndef ONLINE_JUDGE
   freopen("../input.txt", "r", stdin);
   freopen("../output.txt", "w", stdout);
#endif
   InTheNameOfGod;

    ll n, m;
    cin >> n >> m;


    vector<ll> a(n+1), b(m+1);

    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
        kozos.push_back(a[i]);
    }
    for(ll i = 1; i <= m; i++) {
        cin >> b[i];
        kozos.push_back(b[i]);
    }

    sort(kozos.begin(), kozos.end());
    /*cout << "kozos: ";
    for(ll i : kozos) cout << i << ' ';
    cout << endl;*/
    auto it = unique(kozos.begin(), kozos.end());
    kozos.resize((ll)(it - kozos.begin()));

    vector<pair<vector<ll>, vector<ll> > > vals(kozos.size());

    for(ll i = 1; i <= n; i++) {
        a[i] = get_pos(a[i]);
        //cout << a[i] << ' ';
        vals[a[i]].first.push_back(i);
    }
    cout << endl;
    for(ll i = 1; i <= m; i++) {
        b[i] = get_pos(b[i]);
        //cout << b[i] << ' ';
        vals[b[i]].second.push_back(i);
    }
    cout << endl;

    LazyTree aTree = LazyTree(n+1), bTree = LazyTree(m+1);

    for(ll i = 1; i <= n; i++) {
        aTree.update(1, i, i, i);
    }

    set<ll> aSet, bSet;
    for(ll i = 1; i <= m; i++) {
        bSet.insert(i);
    }

    ll mo = 0;
    ll cnt = 0;
    for(auto num : vals) {
        //cout << cnt++ << "\n";

        //cout << "b: \n";
        for(ll ind : num.second) { //b
            auto it = bSet.upper_bound(ind);
            ll end;
            if(it == bSet.end()) end = m+1;
            else end = (*it);

            bTree.update(1, ind, end-1, 1 + bTree.query(1, ind-1, ind-1));
            bSet.erase(ind);

            //cout << ind << ": " << end << endl;
        }
        /*cout << "bSet: ";
        for(ll i : bSet) cout << i << ' ';
        cout << endl;*/

        //calc
        ll aVal = aTree.query(1, 1, n);
        ll bVal = bTree.query(1, 1, m);
        mo = max(mo, aVal * bVal);

        //cout << "query: " << aVal << ", " << bVal << endl;
        //cout << "mo: " << mo << endl;

        //cout << "a: \n";
        for(ll ind : num.first) {//a
            auto it = aSet.lower_bound(ind);
            ll end;
            if(it == aSet.end()) end = n+1; 
            else end = (*it);

            aTree.update(1, ind, end-1, -aTree.query(1, ind, ind));
            aSet.insert(ind);

            //cout << ind << ": " << end << endl;
        }

        /*cout << "aSet: ";
        for(ll i : aSet) cout << i << ' ';
        cout << endl;

        cout << "\n---------\n";*/
    }

    cout << mo;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1964 KiB
2Accepted52ms15232 KiB
subtask214/14
3Accepted3ms2592 KiB
4Accepted3ms2860 KiB
5Accepted3ms3128 KiB
6Accepted3ms2992 KiB
7Accepted3ms3188 KiB
8Accepted3ms3472 KiB
subtask327/27
9Accepted8ms5272 KiB
10Accepted8ms5240 KiB
11Accepted8ms5248 KiB
12Accepted8ms5052 KiB
13Accepted6ms4804 KiB
14Accepted4ms4668 KiB
15Accepted7ms5040 KiB
16Accepted8ms5556 KiB
17Accepted8ms5844 KiB
subtask421/21
18Accepted453ms95068 KiB
19Accepted419ms95760 KiB
20Accepted314ms103600 KiB
21Accepted370ms102972 KiB
22Accepted342ms93008 KiB
23Accepted282ms94264 KiB
24Accepted7ms5840 KiB
subtask50/38
25Time limit exceeded602ms62324 KiB
26Time limit exceeded541ms62548 KiB
27Time limit exceeded565ms62616 KiB
28Time limit exceeded569ms62704 KiB
29Time limit exceeded508ms108868 KiB
30Time limit exceeded569ms108976 KiB
31Accepted388ms109208 KiB
32Accepted391ms98164 KiB
33Accepted395ms98204 KiB
34Accepted212ms81072 KiB
35Accepted335ms92336 KiB
36Time limit exceeded540ms119612 KiB
37Time limit exceeded522ms118860 KiB
38Accepted465ms118500 KiB
39Time limit exceeded565ms63808 KiB
40Time limit exceeded564ms60832 KiB
41Time limit exceeded529ms112396 KiB
42Time limit exceeded551ms54636 KiB
43Accepted430ms102900 KiB
44Accepted470ms107580 KiB