31482023-02-20 17:46:55Szin AttilaMágikus táblázatcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1956 KiB
2Hibás válasz86ms21712 KiB
subtask20/14
3Hibás válasz3ms2592 KiB
4Hibás válasz3ms2848 KiB
5Hibás válasz3ms3060 KiB
6Hibás válasz3ms3228 KiB
7Elfogadva3ms3228 KiB
8Elfogadva3ms3456 KiB
subtask30/27
9Hibás válasz13ms6356 KiB
10Hibás válasz14ms6604 KiB
11Hibás válasz13ms6752 KiB
12Hibás válasz12ms6712 KiB
13Elfogadva8ms6088 KiB
14Hibás válasz4ms5304 KiB
15Hibás válasz9ms6624 KiB
16Hibás válasz13ms7444 KiB
17Elfogadva12ms7260 KiB
subtask40/21
18Időlimit túllépés556ms96740 KiB
19Időlimit túllépés545ms50176 KiB
20Hibás válasz400ms95232 KiB
21Hibás válasz493ms103828 KiB
22Hibás válasz407ms93928 KiB
23Hibás válasz388ms91032 KiB
24Elfogadva8ms6860 KiB
subtask50/38
25Időlimit túllépés606ms96100 KiB
26Időlimit túllépés575ms96036 KiB
27Időlimit túllépés564ms96220 KiB
28Időlimit túllépés578ms96268 KiB
29Időlimit túllépés578ms73404 KiB
30Időlimit túllépés574ms73160 KiB
31Időlimit túllépés561ms73172 KiB
32Időlimit túllépés574ms71436 KiB
33Időlimit túllépés565ms71336 KiB
34Hibás válasz268ms81012 KiB
35Időlimit túllépés550ms61408 KiB
36Időlimit túllépés565ms80308 KiB
37Időlimit túllépés541ms78832 KiB
38Időlimit túllépés586ms72888 KiB
39Időlimit túllépés545ms95968 KiB
40Időlimit túllépés564ms91948 KiB
41Időlimit túllépés546ms84076 KiB
42Időlimit túllépés568ms67596 KiB
43Időlimit túllépés555ms67864 KiB
44Időlimit túllépés578ms71224 KiB