Submission #717216

#	Time	Username	Problem	Language	Result	Execution time	Memory
717216		bachhoangxuan	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	1 ms	340 KiB

kyoto

// 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.se]=0;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.se]=0;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();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60