Submission #943559

#	Time	Username	Problem	Language	Result	Execution time	Memory
943559		andrei_boaca	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	2 ms	856 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
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);
        //assert(dr>poz);
    }
    lines.erase(poz);
    if(st!=0)
    {
        bool prost=0;
        if(st>=poz)
            prost=1;
        //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)
{
    bool ok=0;
    if(poz==450)
    {
        //cout<<"a trecut pe aici\n";
        ok=1;
    }
    auto it=cols.find(poz);
    ll st=0,dr=0;
    if(it!=cols.begin())
        st=*prev(it);
    it++;
    if(it!=cols.end())
    {
        dr=(*it);
        //assert(dr>poz);
    }
    cols.erase(poz);
    if(st!=0)
    {
        bool prost=0;
        if(st>=poz)
            prost=1;
        //assert(st<poz);
        pll val=getval(B[poz]-B[st],poz-st);
        if(setik.find({val,{poz,1}})==setik.end())
            prost=1;
        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;
}

Compilation message (stderr)

kyoto.cpp: In function 'void elimlin(ll)':
kyoto.cpp:42:14: warning: variable 'prost' set but not used [-Wunused-but-set-variable]
   42 |         bool prost=0;
      |              ^~~~~
kyoto.cpp: In function 'void elimcol(ll)':
kyoto.cpp:83:14: warning: variable 'prost' set but not used [-Wunused-but-set-variable]
   83 |         bool prost=0;
      |              ^~~~~
kyoto.cpp:64:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   64 |     bool ok=0;
      |          ^~

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