// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int mod2=1e9+7;
const int maxn=200005;
const int bl=650;
const int maxs=650;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=1000000;
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;n>>=1;
}
return res;
}
int n,m,a[maxn],b[maxn],ans;
int nxta[maxn],nxtb[maxn];
priority_queue<piii> pqa,pqb;
void solve(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=m;i++) cin >> b[i];
for(int i=1;i<=n;i++){
nxta[i]=i+1;
if(i>=2) pqa.push({a[i]-a[i-1],{i-1,i}});
}
for(int i=1;i<=m;i++){
nxtb[i]=i+1;
if(i>=2) pqb.push({b[i]-b[i-1],{i-1,i}});
}
int cx=n,cy=m;
while(!pqa.empty() && !pqb.empty()){
while(!pqa.empty()){
piii x=pqa.top();
if(nxta[x.se.fi]!=x.se.se) pqa.pop();
else break;
}
while(!pqb.empty()){
piii x=pqb.top();
if(nxtb[x.se.fi]!=x.se.se) pqb.pop();
else break;
}
if(pqa.empty() || pqb.empty()) break;
piii x=pqa.top(),y=pqb.top();
if(x.fi>=y.fi){
pqa.pop();
int p=nxta[x.se.se];nxta[x.se.fi]=p;
if(p!=n+1) pqa.push({a[p]-a[x.se.fi],{x.se.fi,p}});
if(cx==x.se.se){ans+=b[cy]*(cx-x.se.fi);cx=x.se.fi;}
}
else{
pqb.pop();
int p=nxtb[y.se.se];nxtb[y.se.fi]=p;
if(p!=m+1) pqb.push({b[p]-b[y.se.fi],{y.se.fi,p}});
if(cy==y.se.se){ans+=a[cx]*(cy-y.se.fi);cy=y.se.fi;}
}
}
ans+=(cy-1)*a[1]+(cx-1)*b[1];
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;//cin >> test;
while(test--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 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 |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
