31522023-02-20 19:08:59Szin AttilaMágikus táblázatcpp14Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1964 KiB
2Elfogadva52ms15232 KiB
subtask214/14
3Elfogadva3ms2592 KiB
4Elfogadva3ms2860 KiB
5Elfogadva3ms3128 KiB
6Elfogadva3ms2992 KiB
7Elfogadva3ms3188 KiB
8Elfogadva3ms3472 KiB
subtask327/27
9Elfogadva8ms5272 KiB
10Elfogadva8ms5240 KiB
11Elfogadva8ms5248 KiB
12Elfogadva8ms5052 KiB
13Elfogadva6ms4804 KiB
14Elfogadva4ms4668 KiB
15Elfogadva7ms5040 KiB
16Elfogadva8ms5556 KiB
17Elfogadva8ms5844 KiB
subtask421/21
18Elfogadva453ms95068 KiB
19Elfogadva419ms95760 KiB
20Elfogadva314ms103600 KiB
21Elfogadva370ms102972 KiB
22Elfogadva342ms93008 KiB
23Elfogadva282ms94264 KiB
24Elfogadva7ms5840 KiB
subtask50/38
25Időlimit túllépés602ms62324 KiB
26Időlimit túllépés541ms62548 KiB
27Időlimit túllépés565ms62616 KiB
28Időlimit túllépés569ms62704 KiB
29Időlimit túllépés508ms108868 KiB
30Időlimit túllépés569ms108976 KiB
31Elfogadva388ms109208 KiB
32Elfogadva391ms98164 KiB
33Elfogadva395ms98204 KiB
34Elfogadva212ms81072 KiB
35Elfogadva335ms92336 KiB
36Időlimit túllépés540ms119612 KiB
37Időlimit túllépés522ms118860 KiB
38Elfogadva465ms118500 KiB
39Időlimit túllépés565ms63808 KiB
40Időlimit túllépés564ms60832 KiB
41Időlimit túllépés529ms112396 KiB
42Időlimit túllépés551ms54636 KiB
43Elfogadva430ms102900 KiB
44Elfogadva470ms107580 KiB