//
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+100,LOG=17,mod=1e9+7;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int n, m, a[maxn], b[maxn];
set <pair <int, pair <pii, int> > > st;
set <int> s[3];
pii pos;
main()
{
IOS
cin >> n >> m;
forn(1, i, n)
{
cin >> a[i];
}
forn(1, j, m)
{
cin >> b[j];
}
forn(1, i, n - 1)
{
st.insert({(a[i + 1] - a[i]), {{i, i + 1}, 1}});
}
forn(1, i, n) s[1].insert(i);
forn(1, j, m) s[2].insert(j);
forn(1, i, m - 1)
{
st.insert({(b[i + 1] - b[i]), {{i, i + 1}, 2}});
}
int was = 0;
int ans = 0;
pos.f = n;
pos.s = m;
while(st.size())
{
auto it = *st.find(*st.rbegin());
// cout << "DELETE " << it.s.f.s << " " << it.s.s << endl;
st.erase(it);
if(it.s.s == 1)
{
s[1].erase(it.s.f.s);
auto it2 = s[1].lower_bound(it.s.f.s);
if(it2 != s[1].end())
{
st.erase({a[*it2] - a[it.s.f.s], {{it.s.f.s, *it2}, 1}});
st.insert({a[*it2] - a[it.s.f.f], {{it.s.f.f, *it2}, 1}});
}
else
{
if(was)
{
// cout << "PLUS!!!!!! " << (pos.s - *s[2].rbegin()) * a[it.s.f.s] << endl;
ans += (pos.s - *s[2].rbegin()) * a[it.s.f.s];
pos.s = *s[2].rbegin();
}
else
{
was = 1;
}
}
}
else
{
s[2].erase(it.s.f.s);
auto it2 = s[2].lower_bound(it.s.f.s);
if(it2 != s[2].end())
{
st.erase({b[*it2] - b[it.s.f.s], {{it.s.f.s, *it2}, 2}});
st.insert({b[*it2] - b[it.s.f.f], {{it.s.f.f, *it2}, 2}});
}
else
{
if(was)
{
// cout << "PLUS!!!!!! " << (pos.f - *s[1].rbegin()) * b[it.s.f.s] << endl;
ans += (pos.f - *s[1].rbegin()) * b[it.s.f.s];
pos.f = *s[1].rbegin();
}
else
{
was = 1;
}
}
}
}
if(pos.f != 1) ans += b[1] * (pos.f-1);
else ans += a[1] * (pos.s-1);
cout << ans;
}
Compilation message
kyoto.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
36 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
