31482023-02-20 17:46:55Szin AttilaMágikus táblázatcpp14Wrong answer 0/100606ms103828 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]);
        vals[a[i]].first.push_back(i);
    }
    for(ll i = 1; i <= m; i++) {
        cin >> b[i];
        mini = min(mini, b[i]);
        vals[b[i]].second.push_back(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
1Wrong answer3ms1956 KiB
2Wrong answer86ms21712 KiB
subtask20/14
3Wrong answer3ms2592 KiB
4Wrong answer3ms2848 KiB
5Wrong answer3ms3060 KiB
6Wrong answer3ms3228 KiB
7Accepted3ms3228 KiB
8Accepted3ms3456 KiB
subtask30/27
9Wrong answer13ms6356 KiB
10Wrong answer14ms6604 KiB
11Wrong answer13ms6752 KiB
12Wrong answer12ms6712 KiB
13Accepted8ms6088 KiB
14Wrong answer4ms5304 KiB
15Wrong answer9ms6624 KiB
16Wrong answer13ms7444 KiB
17Accepted12ms7260 KiB
subtask40/21
18Time limit exceeded556ms96740 KiB
19Time limit exceeded545ms50176 KiB
20Wrong answer400ms95232 KiB
21Wrong answer493ms103828 KiB
22Wrong answer407ms93928 KiB
23Wrong answer388ms91032 KiB
24Accepted8ms6860 KiB
subtask50/38
25Time limit exceeded606ms96100 KiB
26Time limit exceeded575ms96036 KiB
27Time limit exceeded564ms96220 KiB
28Time limit exceeded578ms96268 KiB
29Time limit exceeded578ms73404 KiB
30Time limit exceeded574ms73160 KiB
31Time limit exceeded561ms73172 KiB
32Time limit exceeded574ms71436 KiB
33Time limit exceeded565ms71336 KiB
34Wrong answer268ms81012 KiB
35Time limit exceeded550ms61408 KiB
36Time limit exceeded565ms80308 KiB
37Time limit exceeded541ms78832 KiB
38Time limit exceeded586ms72888 KiB
39Time limit exceeded545ms95968 KiB
40Time limit exceeded564ms91948 KiB
41Time limit exceeded546ms84076 KiB
42Time limit exceeded568ms67596 KiB
43Time limit exceeded555ms67864 KiB
44Time limit exceeded578ms71224 KiB