#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 999999999999999999LL;
int arr1[100005];
int arr2[100005];
struct node{
int s,e;
pair<int,int> v;
node *l,*r;
node (int _s, int _e, bool arr, bool lr){
s = _s; e = _e;
if (s==e){
v = make_pair((arr?arr1:arr2)[s],lr?s:-s);
}
if (s!=e){
l = new node(s,(s+e)/2,arr,lr);
r = new node((s+e)/2+1,e,arr,lr);
v = min(l->v,r->v);
}
}
pair<int,int> qu(int a, int b){
if (a<=s && e<=b){
return v;
}
if (b<=(s+e)/2){
return l->qu(a,b);
}
if (a>(s+e)/2){
return r->qu(a,b);
}
return min(l->qu(a,b),r->qu(a,b));
}
}*r1,*r2,*r3,*r4;
map<pair<int,int>,int> m1,m2;
set<int> s1,s2;
int recl(int a, int b){
//printf("call recl %lld %lld\n",a,b);
if (a==0) return arr1[0]*b;
if (b==0) return arr2[0]*a;
if (m1.count({a,b})) return m1[{a,b}];
auto opt1 = r1->qu(0,a-1);
auto opt2 = r2->qu(0,b-1);
if ((a-opt1.second)*(opt2.first-arr2[b])<(b-opt2.second)*(opt1.first-arr1[a])){
return recl(a,opt2.second)+arr1[a]*(b-opt2.second);
}
else
return recl(opt1.second,b)+arr2[b]*(a-opt1.second);
}
int n,m;
int recr(int a, int b){
//printf("call recr %lld %lld\n",a,b);
if (a==n-1) return arr1[n-1]*(m-1-b);
if (b==m-1) return arr2[m-1]*(n-1-a);
if (m2.count({a,b})) return m2[{a,b}];
auto opt1 = r3->qu(a+1,n-1);
auto opt2 = r4->qu(b+1,m-1);
if ((-opt1.second-a)*(opt2.first-arr2[b])<(-opt2.second-b)*(opt1.first-arr1[a])){
return recr(a,-opt2.second)+arr1[a]*(-opt2.second-b);
}
return recr(-opt1.second,b)+arr2[b]*(-opt1.second-a);
}
main(){
scanf("%lld%lld",&n,&m);
for (int x = 0; x<n; x++){
scanf("%lld",&arr1[x]);
}
for (int x = 0; x<m; x++){
scanf("%lld",&arr2[x]);
}
r1 = new node(0,n-1,true,true);
r2 = new node(0,m-1,false,true);
r3 = new node(0,n-1,true,false);
r4 = new node(0,m-1,false,false);
auto i1 = r1->qu(0,n-1);
auto i2 = r2->qu(0,m-1);
auto i3 = r3->qu(0,n-1);
auto i4 = r4->qu(0,m-1);
int tt = i1.first*(-i4.second-i2.second)+i2.first*(-i3.second-i1.second);
int ans = recl(i1.second,i2.second)+recr(-i3.second,-i4.second)+tt;
printf("%lld",ans);
}
Compilation message
kyoto.cpp:72:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
72 | main(){
| ^~~~
kyoto.cpp: In function 'int main()':
kyoto.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
kyoto.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%lld",&arr1[x]);
| ~~~~~^~~~~~~~~~~~~~~~~
kyoto.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%lld",&arr2[x]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
