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 |