oj.uz

답안 #943546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943546 2024-03-11T15:04:18 Z andrei_boaca Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 2000 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
ll n,m;
ll A[100005],B[100005];
set<ll> lines,cols;
auto comp = [](pair<pll,pll> a, pair<pll,pll> b)
{
    return a.first.first*b.first.second<a.first.second*b.first.first;
};
set<pair<pll,pll>,decltype(comp)> setik(comp); /// 0 -> linie, 1 -> coloana
pll getval(ll a,ll b)
{
    //assert(b!=0);
    if(a==0)
        return {0,1};
    ll g=__gcd(a,b);
    a/=g;
    b/=g;
    return {a,b};
}
void elimlin(ll poz)
{
    auto it=lines.find(poz);
    ll st=0,dr=0;
    if(it!=lines.begin())
        st=*prev(it);
    it++;
    if(it!=lines.end())
        dr=(*it);
    lines.erase(poz);
    if(st!=0)
    {
        assert(poz>st);
        pll val=getval(A[poz]-A[st],poz-st);
        setik.erase({val,{poz,0}});
    }
    if(dr!=0)
    {
        //assert(poz<dr);
        pll val=getval(A[dr]-A[poz],dr-poz);
        setik.erase({val,{dr,0}});
    }
    if(st!=0&&dr!=0)
    {
        //assert(st<dr);
        pll val=getval(A[dr]-A[st],dr-st);
        setik.insert({val,{dr,0}});
    }
}
void elimcol(ll poz)
{
    auto it=cols.find(poz);
    ll st=0,dr=0;
    if(it!=cols.begin())
        st=*prev(it);
    it++;
    if(it!=cols.end())
        dr=(*it);
    cols.erase(poz);
    if(st!=0)
    {
        assert(st<poz);
        pll val=getval(B[poz]-B[st],poz-st);
        setik.erase({val,{poz,1}});
    }
    if(dr!=0)
    {
        //assert(dr>poz);
        pll val=getval(B[dr]-B[poz],dr-poz);
        setik.erase({val,{dr,1}});
    }
    if(st!=0&&dr!=0)
    {
        //assert(st<dr);
        pll val=getval(B[dr]-B[st],dr-st);
        setik.insert({val,{dr,1}});
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        lines.insert(i);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>B[i];
        cols.insert(i);
    }
    ll cnt=2;
    ll x=n;
    ll y=m;
    for(int i=2;i<=n;i++)
        setik.insert({{A[i]-A[i-1],1},{i,0}});
    for(int i=2;i<=m;i++)
        setik.insert({{B[i]-B[i-1],1},{i,1}});
    ll ans=0;
    while(!setik.empty())
    {
        auto it=prev(setik.end());
        if((*it).second.second==0) /// linie
        {
            ll poz=(*it).second.first;
            if(poz==x)
                cnt--;
            if(cnt==0)
            {
                ll aux=*prev(cols.end());
                ans+=(y-aux)*A[poz];
                y=aux;
                cnt=1;
            }
            elimlin(poz);
        }
        else /// coloana
        {
            ll poz=(*it).second.first;
            if(poz==y)
                cnt--;
            if(cnt==0)
            {
                ll aux=*prev(lines.end());
                ans+=(x-aux)*B[poz];
                x=aux;
                cnt=1;
            }
            elimcol(poz);
        }
    }
    /*if(lines.size()==2)
        ans+=(x-1)*B[1]+(y-1)*A[*prev(lines.end())];
    else
        ans+=(x-1)*B[*prev(cols.end())]+(y-1)*A[1];*/
    ans+=(x-1)*B[1]+(y-1)*A[1];
    cout<<ans;
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2052 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2052 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -