31492023-02-20 17:48:04Szin AttilaMágikus táblázatcpp14Wrong answer 0/100579ms117876 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 = 1e9 + 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));
    }
};

int main() {
   InTheNameOfGod;

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

    map<ll, pair<vector<ll>, vector<ll> > > vals;

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

    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
        mini = min(mini, a[i]);
    }
    for(ll i = 1; i <= m; i++) {
        cin >> b[i];
        mini = min(mini, b[i]);
    }

    for(ll i = 1; i <= n; i++) {
        vals[a[i]+mini].first.push_back(i);
    }
    for(ll i = 1; i <= m; i++) {
        vals[b[i]+mini].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.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.second.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
1Accepted3ms1960 KiB
2Wrong answer50ms16780 KiB
subtask20/14
3Wrong answer3ms2708 KiB
4Wrong answer3ms2888 KiB
5Wrong answer3ms3108 KiB
6Wrong answer3ms3360 KiB
7Accepted3ms3304 KiB
8Accepted3ms3524 KiB
subtask30/27
9Wrong answer8ms5524 KiB
10Wrong answer8ms5524 KiB
11Wrong answer8ms5776 KiB
12Wrong answer8ms5692 KiB
13Accepted6ms5120 KiB
14Wrong answer4ms4532 KiB
15Wrong answer7ms5236 KiB
16Wrong answer8ms5684 KiB
17Accepted8ms5928 KiB
subtask40/21
18Wrong answer409ms91664 KiB
19Accepted416ms92212 KiB
20Wrong answer310ms90680 KiB
21Wrong answer342ms99856 KiB
22Wrong answer314ms90412 KiB
23Wrong answer263ms87212 KiB
24Accepted7ms5960 KiB
subtask50/38
25Time limit exceeded574ms70516 KiB
26Time limit exceeded578ms70736 KiB
27Time limit exceeded558ms70668 KiB
28Time limit exceeded579ms71020 KiB
29Time limit exceeded533ms115440 KiB
30Time limit exceeded550ms115368 KiB
31Wrong answer405ms115280 KiB
32Wrong answer444ms107484 KiB
33Wrong answer446ms107480 KiB
34Wrong answer208ms78240 KiB
35Wrong answer379ms97532 KiB
36Time limit exceeded518ms117876 KiB
37Time limit exceeded547ms116560 KiB
38Time limit exceeded524ms114892 KiB
39Time limit exceeded565ms71116 KiB
40Time limit exceeded550ms67928 KiB
41Time limit exceeded546ms63788 KiB
42Time limit exceeded536ms109664 KiB
43Accepted460ms108180 KiB
44Wrong answer490ms113064 KiB