oj.uz

답안 #895158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895158 2023-12-29T13:50:03 Z alexander707070 Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 1 ms 2396 KB 
#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};
      |                 ~~~~^~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -