#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
struct event{
long double diff;
int from,to;
inline friend bool operator < (event fr,event sc){
if(fr.diff!=sc.diff)return fr.diff<sc.diff;
return fr.from<sc.from;
}
}xs,ys,curr;
struct node{
int l,r;
};
int n,m;
long long a[MAXN],b[MAXN],ans;
bool isx,isy;
int xx,yy;
set<event> x,y;
node as[MAXN],bs[MAXN];
void erasea(int x){
as[as[x].l].r=as[x].r;
as[as[x].r].l=as[x].l;
}
void eraseb(int x){
bs[bs[x].l].r=bs[x].r;
bs[bs[x].r].l=bs[x].l;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
as[i].l=i-1; as[i].r=i+1;
if(i>1){
xs={a[i]-a[i-1],i-1,i};
x.insert(xs);
}
}
for(int i=1;i<=m;i++){
cin>>b[i];
bs[i].l=i-1; bs[i].r=i+1;
if(i>1){
ys={b[i]-b[i-1],i-1,i};
y.insert(ys);
}
}
isx=isy=true;
xx=n; yy=m;
while(!x.empty() and !y.empty()){
auto it=x.rbegin(),it2=y.rbegin();
xs=*it; ys=*it2;
if(xs.diff>ys.diff){
x.erase(xs);
if(as[xs.to].r!=n+1){
curr={1.0*(a[as[xs.to].r]-a[xs.to])/(as[xs.to].r-xs.to),xs.to,as[xs.to].r};
x.erase(curr);
x.insert({1.0*(a[as[xs.to].r]-a[xs.from])/(as[xs.to].r-xs.from),xs.from,as[xs.to].r});
}else{
if(isx and isy)isx=false;
else{
isy=true; isx=false;
ans+=(yy-bs[m+1].l)*a[xs.to];
yy=bs[m+1].l;
}
}
erasea(xs.to);
}else{
y.erase(ys);
if(bs[ys.to].r!=m+1){
curr={1.0*(b[bs[ys.to].r]-b[ys.to])/(bs[ys.to].r-ys.to),ys.to,bs[ys.to].r};
y.erase(curr);
y.insert({1.0*(b[bs[ys.to].r]-b[ys.from])/(bs[ys.to].r-ys.from),ys.from,bs[ys.to].r});
}else{
if(isy and isx)isy=false;
else{
isx=true; isy=false;
ans+=(xx-as[n+1].l)*b[ys.to];
xx=as[n+1].l;
}
}
eraseb(ys.to);
}
}
ans+=(xx-1)*b[bs[m+1].l];
ans+=(yy-1)*a[as[n+1].l];
cout<<ans<<"\n";
return 0;
}
Compilation message
kyoto.cpp: In function 'int main()':
kyoto.cpp:45:21: warning: narrowing conversion of '(a[i] - a[(i - 1)])' from 'long long int' to 'long double' [-Wnarrowing]
45 | xs={a[i]-a[i-1],i-1,i};
| ~~~~^~~~~~~
kyoto.cpp:54:21: warning: narrowing conversion of '(b[i] - b[(i - 1)])' from 'long long int' to 'long double' [-Wnarrowing]
54 | ys={b[i]-b[i-1],i-1,i};
| ~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
