31502023-02-20 18:14:58Szin AttilaMágikus táblázatcpp14Hibás válasz 0/100602ms118128 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) {
        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;

int get_pos(int k){
  return (int)(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(int i : kozos) cout << i << ' ';
    cout << endl;*/
    auto it = unique(kozos.begin(), kozos.end());
    kozos.resize((int)(it - kozos.begin()));

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

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

    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;
    for(auto num : vals) {
        //cout << num.first << "\n";

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

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

            //cout << ind << ": " << end << 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 << "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 << "\n---------\n";
    }

    cout << mo;

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Hibás válasz50ms15052 KiB
subtask20/14
3Hibás válasz3ms2412 KiB
4Hibás válasz3ms2688 KiB
5Hibás válasz3ms2916 KiB
6Hibás válasz3ms2704 KiB
7Elfogadva3ms3004 KiB
8Elfogadva3ms3236 KiB
subtask30/27
9Hibás válasz8ms5040 KiB
10Hibás válasz8ms5040 KiB
11Hibás válasz8ms5312 KiB
12Hibás válasz8ms5032 KiB
13Elfogadva6ms4856 KiB
14Hibás válasz4ms4784 KiB
15Hibás válasz7ms5148 KiB
16Hibás válasz8ms5564 KiB
17Elfogadva8ms5568 KiB
subtask40/21
18Hibás válasz423ms92684 KiB
19Elfogadva425ms93308 KiB
20Hibás válasz316ms101208 KiB
21Hibás válasz365ms100948 KiB
22Hibás válasz307ms85228 KiB
23Hibás válasz282ms92452 KiB
24Elfogadva7ms5960 KiB
subtask50/38
25Időlimit túllépés602ms62352 KiB
26Időlimit túllépés552ms62448 KiB
27Időlimit túllépés560ms62376 KiB
28Időlimit túllépés572ms62492 KiB
29Időlimit túllépés515ms107444 KiB
30Időlimit túllépés542ms107440 KiB
31Hibás válasz382ms107352 KiB
32Hibás válasz388ms97604 KiB
33Hibás válasz372ms97740 KiB
34Hibás válasz201ms79464 KiB
35Hibás válasz340ms91396 KiB
36Hibás válasz481ms118128 KiB
37Hibás válasz497ms117424 KiB
38Hibás válasz446ms116660 KiB
39Időlimit túllépés569ms63492 KiB
40Időlimit túllépés577ms60640 KiB
41Időlimit túllépés532ms57844 KiB
42Elfogadva479ms104344 KiB
43Elfogadva430ms102452 KiB
44Hibás válasz465ms107016 KiB