31502023-02-20 18:14:58Szin AttilaMágikus táblázatcpp14Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Wrong answer50ms15052 KiB
subtask20/14
3Wrong answer3ms2412 KiB
4Wrong answer3ms2688 KiB
5Wrong answer3ms2916 KiB
6Wrong answer3ms2704 KiB
7Accepted3ms3004 KiB
8Accepted3ms3236 KiB
subtask30/27
9Wrong answer8ms5040 KiB
10Wrong answer8ms5040 KiB
11Wrong answer8ms5312 KiB
12Wrong answer8ms5032 KiB
13Accepted6ms4856 KiB
14Wrong answer4ms4784 KiB
15Wrong answer7ms5148 KiB
16Wrong answer8ms5564 KiB
17Accepted8ms5568 KiB
subtask40/21
18Wrong answer423ms92684 KiB
19Accepted425ms93308 KiB
20Wrong answer316ms101208 KiB
21Wrong answer365ms100948 KiB
22Wrong answer307ms85228 KiB
23Wrong answer282ms92452 KiB
24Accepted7ms5960 KiB
subtask50/38
25Time limit exceeded602ms62352 KiB
26Time limit exceeded552ms62448 KiB
27Time limit exceeded560ms62376 KiB
28Time limit exceeded572ms62492 KiB
29Time limit exceeded515ms107444 KiB
30Time limit exceeded542ms107440 KiB
31Wrong answer382ms107352 KiB
32Wrong answer388ms97604 KiB
33Wrong answer372ms97740 KiB
34Wrong answer201ms79464 KiB
35Wrong answer340ms91396 KiB
36Wrong answer481ms118128 KiB
37Wrong answer497ms117424 KiB
38Wrong answer446ms116660 KiB
39Time limit exceeded569ms63492 KiB
40Time limit exceeded577ms60640 KiB
41Time limit exceeded532ms57844 KiB
42Accepted479ms104344 KiB
43Accepted430ms102452 KiB
44Wrong answer465ms107016 KiB