Submission #1117261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117261		imarn	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	117 ms	17856 KiB

kyoto

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
struct line{
    ll a,b,c,d;
    bool operator<(const line &o)const{
        return a*o.b<o.a*b;
    }
};
const int mxn=1e5+5;
bool dla[mxn]{0},dlb[mxn]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int h,w;cin>>h>>w;
    ll a[h+1],b[w+1];
    int la[h+2],ra[h+2],lb[w+2],rb[w+2];
    for(int i=1;i<=h;i++)cin>>a[i],la[i]=i-1,ra[i]=i+1;
    for(int i=1;i<=w;i++)cin>>b[i],lb[i]=i-1,rb[i]=i+1;
    priority_queue<line>qa,qb;
    for(int i=2;i<=h;i++)qa.push({a[i]-a[i-1],1,i-1,i});
    for(int i=2;i<=w;i++)qb.push({b[i]-b[i-1],1,i-1,i});
    ll rs=0;int lsa=h,lsb=w;
    while(!qa.empty()||!qb.empty()){
        if(!qb.empty()&&(qa.empty()||qa.top()<qb.top())){
            auto u=qb.top();qb.pop();
            if(dlb[u.c]||dlb[u.d])continue;
            //cout<<b[u.c]<<' '<<b[u.d]<<" B\n";
            if(u.d==lsb){
                rs+=u.b*a[lsa];
                lsb-=u.b;
            }dlb[u.d]=1;
            rb[u.c]=rb[u.d];
            lb[rb[u.d]]=u.c;
            if(u.c!=0&&rb[u.d]!=w+1)qb.push({b[rb[u.d]]-b[u.c],rb[u.d]-u.c,u.c,rb[u.d]});
        }
        else {
            auto u=qa.top();qa.pop();
            if(dla[u.c]||dla[u.d])continue;
            //cout<<a[u.c]<<' '<<a[u.d]<<" A\n";
            if(u.d==lsa){
                rs+=u.b*b[lsb];
                lsa-=u.b;
            }dla[u.d]=1;
            ra[u.c]=ra[u.d];
            la[ra[u.d]]=u.c;
            if(u.c!=0&&ra[u.d]!=h+1)qa.push({a[ra[u.d]]-a[u.c],ra[u.d]-u.c,u.c,ra[u.d]});
        }
    }cout<<rs;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:28:9: warning: variable 'la' set but not used [-Wunused-but-set-variable]
   28 |     int la[h+2],ra[h+2],lb[w+2],rb[w+2];
      |         ^~
kyoto.cpp:28:25: warning: variable 'lb' set but not used [-Wunused-but-set-variable]
   28 |     int la[h+2],ra[h+2],lb[w+2],rb[w+2];
      |                         ^~

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