제출 #895160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895160		alexander707070	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	367 ms	21332 KiB

kyoto

#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);
        }
    }
    as[0].r=1; as[n+1].l=n;

    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);
        }
    }
    bs[0].r=1; bs[m+1].l=m;

    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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:56:21: warning: narrowing conversion of '(b[i] - b[(i - 1)])' from 'long long int' to 'long double' [-Wnarrowing]
   56 |             ys={b[i]-b[i-1],i-1,i};
      |                 ~~~~^~~~~~~

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