31492023-02-20 17:48:04Szin AttilaMágikus táblázatcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1960 KiB
2Hibás válasz50ms16780 KiB
subtask20/14
3Hibás válasz3ms2708 KiB
4Hibás válasz3ms2888 KiB
5Hibás válasz3ms3108 KiB
6Hibás válasz3ms3360 KiB
7Elfogadva3ms3304 KiB
8Elfogadva3ms3524 KiB
subtask30/27
9Hibás válasz8ms5524 KiB
10Hibás válasz8ms5524 KiB
11Hibás válasz8ms5776 KiB
12Hibás válasz8ms5692 KiB
13Elfogadva6ms5120 KiB
14Hibás válasz4ms4532 KiB
15Hibás válasz7ms5236 KiB
16Hibás válasz8ms5684 KiB
17Elfogadva8ms5928 KiB
subtask40/21
18Hibás válasz409ms91664 KiB
19Elfogadva416ms92212 KiB
20Hibás válasz310ms90680 KiB
21Hibás válasz342ms99856 KiB
22Hibás válasz314ms90412 KiB
23Hibás válasz263ms87212 KiB
24Elfogadva7ms5960 KiB
subtask50/38
25Időlimit túllépés574ms70516 KiB
26Időlimit túllépés578ms70736 KiB
27Időlimit túllépés558ms70668 KiB
28Időlimit túllépés579ms71020 KiB
29Időlimit túllépés533ms115440 KiB
30Időlimit túllépés550ms115368 KiB
31Hibás válasz405ms115280 KiB
32Hibás válasz444ms107484 KiB
33Hibás válasz446ms107480 KiB
34Hibás válasz208ms78240 KiB
35Hibás válasz379ms97532 KiB
36Időlimit túllépés518ms117876 KiB
37Időlimit túllépés547ms116560 KiB
38Időlimit túllépés524ms114892 KiB
39Időlimit túllépés565ms71116 KiB
40Időlimit túllépés550ms67928 KiB
41Időlimit túllépés546ms63788 KiB
42Időlimit túllépés536ms109664 KiB
43Elfogadva460ms108180 KiB
44Hibás válasz490ms113064 KiB