3148 2023. 02. 20 17:46:55 Szin Attila Mágikus táblázat cpp14 Hibás válasz 0/100 606ms 103828 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Hibás válasz 3ms 1956 KiB
2 Hibás válasz 86ms 21712 KiB
subtask2 0/14
3 Hibás válasz 3ms 2592 KiB
4 Hibás válasz 3ms 2848 KiB
5 Hibás válasz 3ms 3060 KiB
6 Hibás válasz 3ms 3228 KiB
7 Elfogadva 3ms 3228 KiB
8 Elfogadva 3ms 3456 KiB
subtask3 0/27
9 Hibás válasz 13ms 6356 KiB
10 Hibás válasz 14ms 6604 KiB
11 Hibás válasz 13ms 6752 KiB
12 Hibás válasz 12ms 6712 KiB
13 Elfogadva 8ms 6088 KiB
14 Hibás válasz 4ms 5304 KiB
15 Hibás válasz 9ms 6624 KiB
16 Hibás válasz 13ms 7444 KiB
17 Elfogadva 12ms 7260 KiB
subtask4 0/21
18 Időlimit túllépés 556ms 96740 KiB
19 Időlimit túllépés 545ms 50176 KiB
20 Hibás válasz 400ms 95232 KiB
21 Hibás válasz 493ms 103828 KiB
22 Hibás válasz 407ms 93928 KiB
23 Hibás válasz 388ms 91032 KiB
24 Elfogadva 8ms 6860 KiB
subtask5 0/38
25 Időlimit túllépés 606ms 96100 KiB
26 Időlimit túllépés 575ms 96036 KiB
27 Időlimit túllépés 564ms 96220 KiB
28 Időlimit túllépés 578ms 96268 KiB
29 Időlimit túllépés 578ms 73404 KiB
30 Időlimit túllépés 574ms 73160 KiB
31 Időlimit túllépés 561ms 73172 KiB
32 Időlimit túllépés 574ms 71436 KiB
33 Időlimit túllépés 565ms 71336 KiB
34 Hibás válasz 268ms 81012 KiB
35 Időlimit túllépés 550ms 61408 KiB
36 Időlimit túllépés 565ms 80308 KiB
37 Időlimit túllépés 541ms 78832 KiB
38 Időlimit túllépés 586ms 72888 KiB
39 Időlimit túllépés 545ms 95968 KiB
40 Időlimit túllépés 564ms 91948 KiB
41 Időlimit túllépés 546ms 84076 KiB
42 Időlimit túllépés 568ms 67596 KiB
43 Időlimit túllépés 555ms 67864 KiB
44 Időlimit túllépés 578ms 71224 KiB